Tree day — Level Order Traversal, Validate BST, and LCA of a BST with its whole follow-up tree. Notes:
- Level Order didn't need a new pattern at all — it's Rotting Oranges' snapshot-queue trick, just pointed at a tree's two children instead of a grid's four directions. No
visitedneeded this time, since a tree has exactly one path to every node - Zigzag, Right Side View, and Average of Levels are all the same skeleton with one line of collection logic swapped — reverse the list, keep only the last node, or track a sum instead of a list
- Validate BST's real trap: comparing a node only to its immediate parent misses violations from higher up.
5 → (3, 8),8 → (2, 9)— every parent-child pair looks fine, but2sits in5's right subtree where everything must be bigger than 5. Each node needs a range from every ancestor, not just one - The in-order alternative reframes the whole problem: a valid BST's in-order walk is just a strictly increasing sequence, so I only need to remember the last value and compare
- Iterative in-order needed a separate cursor variable (
node) outside the stack, unlike every other iterative conversion today — because "dive left as far as possible" is a sequential procedure, not an independent unit of work I can just push and pop - LCA of a BST: walking down while both targets agree on direction is really retracing the shared prefix of both root-to-node paths. The moment they'd need different directions is exactly where those paths split — that's the LCA
- LCA with parent pointers turned out to be Linked List Intersection wearing a tree costume — same two-pointer distance-equalizing trick, redirecting each pointer to the other's start once it runs dry
- Bugs today were all "grabbed the wrong similarly-named thing":
while stackinstead ofwhile node,node = qinstead ofnode == q,returninstead ofreturn node— reinforced the habit of reading each condition out loud before moving on