A linked list that
learned to branch

Chapter 10's node was a value and one next pointer. Give it a second pointer and rename them left and right: that's the whole data structure. A binary tree is boxes-and-arrows where every box points down at up to two others, nothing points back up, and nothing ever forms a loop — n nodes, n−1 arrows, exactly one path from the top to anywhere.

Five words of vocabulary buy the rest of the chapter: the root (the one node nobody points at), a leaf (a node pointing at nothing), a node's depth (arrows from the root down to it), the tree's height (the longest root-to-leaf walk), and balanced (height ≈ log₂ n, the bushy ideal) versus skewed (every node has one child — a linked list in a tree costume, height = n). That last distinction decides space costs in Section 8, so keep it warm.

DFS is the maze-runner strategy: at every fork, commit to one corridor, walk it to the dead end, then backtrack to the last fork and take the corridor you skipped. On a binary tree the whole strategy is three lines — do something at this node, recurse left, recurse right — and the "backtrack" step costs you nothing to write, because returning from a function call is backtracking.

What makes DFS the default tool is what it knows while it runs: at any moment it is standing on one node holding the entire root-to-here path in its pocket. Anything phrased in terms of depth, ancestors, paths, or "does this whole subtree satisfy X" is DFS territory, because those questions are exactly what the pocket answers. Maximum Depth Easy, Same Tree Easy, and Invert Binary Tree Easy are all this three-liner with a different middle line — we'll collect them in Section 7.

Here's the part textbooks over-mystify. Pre-order, in-order, and post-order are not three algorithms. They are one algorithm — "recurse left, recurse right" — with a single choice left open: when do you look at the node you're standing on?

• Pre-order — look before visiting either child. "Deal with me first, then my descendants." The order you'd copy or serialize a tree in, because a parent must exist before its children can be attached.
• In-order — look between the children: all of the left subtree, then me, then all of the right. On a BST this emits the values in sorted order — hold that thought.
• Post-order — look after both children. "Descendants first." The order for anything computed from child results — heights, sizes, safe deletion — because both answers are on the table before you speak.

Press the four buttons below on the same tree and watch when each traversal's spotlight lands. (The fourth button cheats — it visits by floors, and it's the subject of Section 5.)

Where does the maze-runner keep the "way back"? In Chapter 8 you'd have reached for an explicit stack — and you still can: push the root, pop a node, look at it, push its children, repeat. That loop is DFS. The recursive version is the same algorithm with one difference: the language's call stack holds the frames for you. Every visit(node.left) call pushes; every return pops. Recursion isn't a fourth traversal — it's the stack version with the stack outsourced.

Watch it happen. The widget runs a real pre-order DFS while drawing the actual stack frames next to the tree. Two things to notice: the stack's contents at any moment are exactly the root-to-current-node path (Section 2's "pocket"), and the tallest the stack ever gets equals the tree's height — which is why Maximum Depth Easy is secretly the question "how tall did the stack get?".

Some questions don't care about depth at all — they care about breadth: "give me the values level by level", "the average of each level", "zigzag the floors". Diving deep is the wrong shape for those; you want to sweep the building one floor at a time. That's BFS, and its whole machinery is a queue: start with the root inside, and repeatedly pop a node, look at it, push its children. First-in-first-out guarantees floor 1 finishes before floor 2 begins.

The plain loop visits nodes in floor order but never tells you where one floor ends — and Level Order Traversal Medium wants the floors grouped. The fix is the one genuinely clever line in all of BFS, the snapshot trick: at the top of each round, freeze width = len(queue). Every node currently in the queue is on this floor; everything pushed during the round is on the next one. Pop exactly width nodes, and the inner loop emits one clean floor. That's the flagship code in Section 9.

Once floors are cheap, a family of Mediums collapses into one-line edits. Right Side View Medium: stand to the tree's right, report what you can see — which is exactly the last node of each floor. Run level order, keep floor[-1], done. Zigzag Level Order: reverse every other floor. Level averages: sum(floor)/len(floor). The traversal is the product; each problem is a garnish.

The widget sweeps the floors with a camera. Watch floor 4 closely: its rightmost node, 8, hangs under the left subtree — which is exactly why the tempting shortcut "just follow right-child pointers down" is wrong. The camera sees whatever floor sticks out farthest, no matter whose subtree it grew from.

For the record, DFS can moonlight here too: recurse right-child-first, track depth, and keep the first node you reach on each new depth. Same answer, O(h) space instead of O(w). Knowing both — and saying which you'd pick and why — is exactly the "names the pattern" dial from Chapter 1.

Here is this chapter's practice set, each reduced to its essence. Notice how five of the six are the DFS three-liner with a different middle:

• Invert Binary Tree Easy — at every node, swap the children; recurse. Any order works. (Famously, the creator of Homebrew reported being rejected at Google over this one. You will not be.)
• Maximum Depth Easy — 1 + max(depth(l), depth(r)), empty tree is 0. Post-order: the children answer first.
• Same Tree Easy — both empty → true; one empty or values differ → false; else recurse both sides and and the answers. Two trees walked in lock-step.
• Diameter of Binary Tree Easy — sneaky: the function returns height, but at every node it also considers height(l) + height(r) as a candidate for a global best. Returning one thing while harvesting another is the bottom-up shape Chapter 12 makes official.
• Level Order Traversal Medium — the queue plus the snapshot trick; flagship, next section.
• Right Side View Medium — level order, keep the last of each floor. You just watched it.

The decision is a coin with clean faces. Vertical words — depth, path, ancestor, subtree property, "does the whole tree…" — take DFS, because the recursion carries the root-to-here path for free. Horizontal words — level, floor, zigzag, view, "nearest" on an unweighted structure — take BFS, because the queue serves floors in order. Both are O(n) time; the real difference is what they hold: DFS keeps a path, O(h) — about log₂ n balanced, n skewed — while BFS keeps a floor, O(w) — up to n/2 on the bottom of a bushy tree. Tall skinny tree? BFS is cheap. Short bushy tree? DFS is. Say this trade-off unprompted and watch the verification dial from Chapter 1 twitch upward.

The pattern, as a whiteboard skeleton:

1. 1Empty check first. if root is None: return base — the base is 0, [], or True, and it falls out of the problem statement.
2. 2Name the ask. Vertical words (depth / path / subtree) → DFS. Horizontal words (level / view / zigzag) → BFS. Say the choice out loud.
3. 3DFS: write the three-liner. A function that calls itself on left and right, plus one line of local work — then choose when that line runs: pre, in, or post.
4. 4Building from child answers? Post-order: combine the two returned values (max, +, ==) on the way back up.
5. 5BFS: queue seeded with the root. While non-empty: freeze width = len(q), pop exactly width nodes, push their children — that inner loop is one floor.
6. 6Trace three shapes: the empty tree, a single node, and a skewed stick. Tree bugs live at None and at one-child nodes.
7. 7State the cost: O(n) time — every node once; O(h) stack for DFS, O(w) queue for BFS, and which of h or w is scarier for this input.

Level Order Traversal Medium: return the tree's values grouped by floor. Everything you need is Section 5 verbatim — a queue, and the frozen width that marks where a floor ends. The Python is the interview-standard imperative loop; the Scala version makes the floor structure explicit by treating each whole frontier as one value and mapping it to the next. Same algorithm, two accents — and Right Side View falls out of either as a one-liner, which is the "traversal is the product" point made executable.

Read the Python inner loop twice — it's the part people fumble live. width is captured before the loop, so the children appended during the round are never popped in it: this floor and the next can share a queue without bleeding into each other. That single frozen variable is the difference between "BFS visits in level order" (true, easy) and "BFS returns the levels" (the actual question).