Week 3 — Trees Intro: Recursion as the Default Tool

Theme: Binary trees are recursion’s natural habitat. Five problems that drill the “what does this function return for a subtree?” framing until it’s reflex. Time budget: ~6 hours focused work; ~10 hours including the LC bank. Hard rule: every problem solved twice — recursive first, then iterative (BFS/DFS-stack). No exceptions. Interviewers ask “what if recursion stack overflows?”

Why this week

Tree problems are the single largest topic family in mid/senior coding rounds (≈30% of all phone screen problems at FAANG). They look easy individually — each one is 10-20 lines — but candidates who never internalize the “what does my recursive call return?” discipline get bitten on the next-level problems (LCA, path sum, serialize, segment trees, etc.).

This week trains exactly that reflex:

  • p11: function returns the (mutated) subtree root — base case is the null subtree.
  • p12: function returns an integer (depth) — base case returns 0.
  • p13: function returns a boolean — base case is both-null vs one-null.
  • p14: function returns AN ANSWER to a sub-problem (height) while also UPDATING a global (diameter) — the “global + return value” two-channel pattern.
  • p15: function takes TWO subtree pointers — the “mirror walk” generalization that reappears in LC 100, 572, 1367.

By Friday you should be able to write any of these in <5 minutes, both recursively and iteratively, and articulate the base case before the recursive case.

Flagship problems (the 5 you OWN this week)

#ProblemLCDifficultyWhy this one
p11Invert Binary Tree226EasyThe “Homebrew” question. Trains the “return the mutated subtree” pattern.
p12Maximum Depth of Binary Tree104EasyTrains “function returns an integer aggregate from children.”
p13Same Tree100EasyTrains “function takes TWO trees” — the parallel-walk pattern.
p14Diameter of Binary Tree543Easy (deceptively)The two-channel pattern: return one thing, update another globally. The single most important tree trick.
p15Symmetric Tree101EasyGeneralizes p13 — mirror walk. Sets up LC 951 (Flip Equivalent).

LC bank (~25 problems for spaced repetition)

Mirror / structure equality:

  • LC 226 (p11), LC 100 (p13), LC 101 (p15), LC 572 Subtree of Another, LC 951 Flip Equivalent, LC 1367 Linked List in Binary Tree

Depth / height:

  • LC 104 (p12), LC 111 Min Depth, LC 110 Balanced Binary Tree, LC 559 Max Depth N-ary, LC 543 (p14)

Traversal mechanics:

  • LC 144 Preorder, LC 94 Inorder, LC 145 Postorder, LC 102 Level Order, LC 103 Zigzag, LC 199 Right Side View, LC 107 Bottom-Up Level Order

Construction / manipulation:

  • LC 108 Sorted Array to BST, LC 617 Merge Two Binary Trees, LC 1325 Delete Leaves with Given Value

Path / aggregate:

  • LC 112 Path Sum, LC 257 Binary Tree Paths, LC 404 Sum of Left Leaves, LC 129 Sum Root-to-Leaf Numbers

Readiness gate (binary; must all be YES before Week 4)

  • I can write TreeNode from memory: __slots__ = ("val", "left", "right").
  • I solved each of p11–p15 in BOTH recursive AND iterative form.
  • I can recite the “what does my recursive call return for a subtree?” framing for each.
  • I can convert any recursive tree solution to iterative (BFS deque OR DFS stack) without looking up syntax.
  • I know sys.setrecursionlimit(10_000) and why production code should iterative if depth can exceed ~1000.
  • I can articulate the “two-channel pattern” from p14: function returns one thing (height) but a closure variable accumulates another (diameter).
  • I can solve LC 100 (Same Tree) and LC 101 (Symmetric Tree) and explain why they are the same algorithm with different mirror logic.
  • My stress_test() for each problem cross-checks recursive vs iterative on 1000 random trees built with random.Random(42).

If ANY unchecked: do not start Week 4. Re-drill the missing pieces.

Recurring traps (steal these for the interview)

  1. Forgetting the null base case. Every tree recursion must handle if not node: return <base> FIRST.
  2. Returning the wrong thing from recursion. Write out “what does this function return?” in English BEFORE coding. p11 returns the mutated subtree root. p12 returns an int. p13 returns a bool. p14 returns height but updates a global. p15 takes TWO nodes.
  3. Iterative depth using len(stack) as depth. That’s the current path length not the max depth seen. You need level-by-level BFS or to pair (node, depth) in the stack.
  4. Mutating during traversal. p11 mutates. p12-p15 don’t. State which mode aloud.
  5. Stack overflow. LC test cases occasionally include skewed trees of depth 10^4. Recursive Python hits the recursion limit at ~1000. Bump with sys.setrecursionlimit(10_000) OR use iterative.

Stretch (only if you finish all 5 + LC bank with time left)

  • LC 124 Binary Tree Maximum Path Sum (Hard) — generalizes p14’s two-channel pattern with negatives. Highly testable at Staff level.
  • LC 297 Serialize and Deserialize Binary Tree (Hard) — recursion + parsing. Common at Meta.
  • LC 236 Lowest Common Ancestor — the canonical “return multiple things via tuple from recursion” problem.

Begin with p11 — Invert Binary Tree.