Tree Recursion

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   Tree recursion: f(node) = combine(f(left), f(right), node). Trust the child calls; write only the base case and the combine step.

   #1
2. ↯use it when

   Children's answers needed (height, balanced, count) → return up. Ancestors' context needed (depth, remaining sum, max so far) → pass down.

   #2
3. { }template

   int f(TreeNode n) { if (n == null) return 0; int l = f(n.left), r = f(n.right); best = Math.max(best, l + r); return 1 + Math.max(l, r); }

   #3
4. O( )cost

   One pass: O(n) time, O(h) stack — about 20 frames for a balanced 10⁶-node tree, 10⁶ for a chain. Recomputing height per node: O(n²).

   #4
5. !trap

   Returning the answer instead of what the parent needs: Diameter returns the height and records left + right — never returns the bend.

   #5
6. !trap

   Paths end only at a leaf (left == null && right == null), never at null. Save new ArrayList<>(path), then path.remove(path.size() - 1).

   #6
7. !trap

   best = 0 with negative values: Max Path Sum on [-3] must give −3. Start at Integer.MIN_VALUE, reset it in the public method.

   #7
8. ✦pro tip

   Any downward path sums to k: prefix sums of the current path in a HashMap seeded {0: 1}; look up sum − k, add sum, recurse, take it back out.

   #8
9. ✦pro tip

   LCA: return root if it's null, p or q; if both sides report something, root is the split point.

   #9
10. ✦pro tip

    Rebuild: next preorder value (or postorder from the back) = root; a HashMap of inorder positions splits left/right; build left first (right first for postorder).

    #10

Shaky on a card? Open the chapter or flip its recall cards.