Tree Traversal

Every web page you load is a tree (the DOM), every directory you `cd` into is a tree, every JSON document with nested objects is a tree, and every arithmetic expression a compiler parses is a tree. **Binary Tree Fundamentals** turns that ubiquitous shape into a precise data structure where each node has at most two children, named `left` and `right`. This lesson covers the vocabulary you need for the rest of the curriculum (root, leaf, parent, child, sibling, depth, height), the four common shape categories (full, complete, perfect, balanced) and the degenerate case that collapses to a chain, all four canonical traversals (preorder, inorder, postorder, and level-order BFS), and both recursive and iterative implementations of each. You will also analyze why traversals are `O(n)` time but only `O(h)` space when written recursively. In **Queue & Deque**, you saw that a FIFO queue processes items in arrival order; level-order traversal is exactly that pattern applied to tree nodes. In **Hash Map (Dictionary) Basics**, the bucket-by-key idea reappears here when you store parent-pointer mappings or memoize subtree results during a traversal. With binary trees in your toolkit, **Binary Search Tree (BST)** layers an ordering invariant on top to turn the same shape into a logarithmic-time search structure.

An invert-binary-tree problem famously got Max Howell rejected from Google in 2015, and the joke landed because the canonical solution is three lines of recursion. Trees show up everywhere in interviews precisely because they reward a particular kind of thinking: the answer for a node is almost always a function of the answers for its left and right subtrees, computed recursively, combined at the parent. **Tree Algorithms** trains that decomposition habit across a wide range of problems. You will implement BST insert, search, delete, validation, and the kth-smallest in-order trick. You will compute lowest common ancestor in both a generic binary tree and a BST. You will measure height, diameter, and width, and walk through path-sum problems, root-to-leaf enumeration, and the deceptively tricky maximum-path-sum-between-any-two-nodes. Structural operations include invert, mirror check, flatten to linked list, and serialize and deserialize. The lesson finishes with reconstructing a tree from inorder plus preorder or inorder plus postorder. In **Trees: Binary Tree Fundamentals**, you learned how nodes, children, and the four traversal orders work. **Recursion Fundamentals** gave you the call-stack mental model that every tree algorithm here relies on; tree recursion is essentially recursion with two recursive calls per frame. Next, **Graph Algorithms (Core)** removes the tree assumption (no cycles, no shared nodes) and tackles the more general traversal problems that result.