Trees, No Gaps
Traversal · Tree Recursion · Binary Search Trees — a complete, prerequisite-ordered path through 28 sub-variants, with compiled Java 21 templates, failure-mode tables, a recognition guide, and per-sub-variant mastery gates.
Calibration: written for an advanced backend engineer doing FAANG prep in Java 21, LeetCode-numbered, and shaped as a companion to Three Patterns, No Gaps. The level bracket is left open, so the doc is tiered instead of guessed: the ★ core path is the minimum sufficient set (a strong beginner can follow it linearly), ○ marks optional depth, and Extra Reps are pure repetition — skip them if the starred problem went clean the first time.
Total core: 58 problems — 52 ★ plus 6 ⚠︎. Everything else is explicitly labelled optional. Nothing here is padding; if a problem is listed, there is exactly one thing it teaches that no earlier problem taught.
Every template in this document was compiled and run against the listed cases before being written down.
How to read the tables#
| Marker | Meaning |
|---|---|
| ★ | Core. Must solve unaided, from scratch, before advancing. |
| ○ | Optional. Solve only if the gate check for that sub-variant fails, or you want depth. |
| PRO | LeetCode Premium. Free substitute given where one exists. |
| ⚠︎ | Anti-pattern problem. Included specifically because the obvious recursion is wrong. These are the highest-value problems in the entire document. |
Problems within a sub-variant are in strict prerequisite order. Sub-variants themselves are in prerequisite order.
Two conventions used throughout, because they remove more bugs than anything else:
- A tree question is answered by exactly one of three machines — a traversal (I need to visit), a recursion that returns a value (I need to aggregate), or an ordering argument (it is a BST, so I need to decide which subtree to skip). Naming the machine before writing code is the entire skill.
nullis a case, not an accident. Every template below states what it returns fornulland why that value is the identity element of whatever it is combining.
4 — RECOGNITION GUIDE#
4.1 The decision procedure#
Run these in order. Stop at the first match.
Step 0 — Is it actually a binary tree? If the input is n nodes plus an edge list, it is a tree as a graph: build an adjacency list, pick a root, and pass the parent down to avoid revisiting. Half the "hard tree" problems are ordinary DFS wearing an unfamiliar input format. If the input is a TreeNode, continue.
Step 1 — Is it a BST? Say it out loud, because it is the highest-leverage fact available. If yes, one comparison per node must eliminate a subtree — §3.A/G — and inorder is sorted, so any order-statistic question is a scan over a sorted sequence — §3.C. A BST problem solved with a general tree traversal is a wrong answer with the right output.
Step 2 — Does the question mention distance, direction, or "nearest" in any sense that is not strictly downward? Ancestors, cousins, "within k of a node", spreading, burning, "closest leaf". → The tree is a graph. Parent map, BFS, visited — §1.F. No top-down recursion can answer these, and no amount of augmenting the return value will fix it.
Step 3 — Does the answer depend on depth or level? Levels, rows, "each level", "the rightmost node", widths, zigzag. → BFS with the size snapshot — §1.C/D. The DFS alternative (carry depth down and index an accumulator by it) is usually shorter and O(h) space; know both and say which you chose and why.
Step 4 — Does every node need its own answer? "For each node, compute…", or an answer array of length n. → Two passes: bottom-up to collect subtree facts, top-down to combine them with the outside-the-subtree part — §2.L. A single DFS here is O(n²).
Step 5 — Otherwise it is a recursion. Answer the three questions before writing code.
| Question | If the answer is… | Then |
|---|---|---|
What does dfs return? | one fact about the subtree | §2.A bottom-up aggregate |
| the value the parent needs, while the answer is recorded on the side | §2.C augmented return | |
| a small tuple, one entry per state | §2.K tree DP | |
| the rebuilt or rewired subtree | §2.H / §2.J | |
| What flows down? | a running max, a running number, a bound | §2.D inherited state |
| a mutable path or map that must be undone | §2.E / §2.F backtracking | |
What is the null value? | not obvious | you have not finished designing the state. Go back. |
Step 6 — Is there an O(1)-space constraint, or a follow-up asking for one? → Morris threading for traversal (§1.G), the splice-based flatten (§2.J), or the "previous level is the queue" trick (#60). These are the only three O(1)-space tree techniques worth memorising.
Step 7 — Is the tree given as a serialized string, or must you produce one? → Preorder with explicit null markers, one shared cursor for reading — §2.I. Inorder alone can never work; level-order works but is longer to write.
4.2 Signal → pattern cheat table#
| Signal in the problem statement | Most likely | Watch out for |
|---|---|---|
| "level", "row", "each level", "zigzag" | BFS with the size snapshot | The DFS-with-depth version is often shorter |
| "rightmost/leftmost node of each level" | BFS last-of-level, or DFS right-first | Right-first DFS records on first arrival at a depth |
| "distance k from a node", "burning", "cousins" | Parent map + BFS + visited | A pure top-down DFS cannot express it at all |
| "root-to-leaf" | Backtracking, §2.E | A leaf is left == null && right == null |
| "any path" / "path between any two nodes" | Augmented return, §2.C | Record the bend, return the continuation |
| "number of paths summing to K" | Prefix map on the root path, §2.F | Undo the map entry on the way up |
| "for each node, compute X" | Rerooting, two passes, §2.L | One DFS is O(n²) |
| "the tree is complete / perfect / balanced" | The shape is the algorithm | 222 is O(log²n), not O(n) |
| "BST" + "k-th / closest / successor / minimum difference" | Inorder scan with one prev variable, §3.C/D | The answer is often not at the node you stop on |
| "BST" + "range / trim / greater sum" | Pruned descent, §3.G | Returning null for an out-of-range node deletes valid descendants |
| "validate BST" | Inherited (low, high) bounds | Parent comparison is the classic wrong answer |
| "serialize", "encode", "same structure" | Preorder + null markers, §2.I | Inorder is not uniquely decodable |
| "constant extra space" on a traversal | Morris threading, §1.G | You must undo the thread |
| "n nodes, edges[i] = [a, b]" | Adjacency list + DFS with a parent parameter | There is no root until you pick one |
| "children" (plural, a list) | N-ary generalization, §1.H | The identity element for an empty child list |
| "sorted array/list" → tree | Middle element as root, §3.F | Inserting one at a time degenerates to a list |
4.3 Trap cases — where the obvious approach is wrong#
| Problem | The obvious (wrong) read | Why it fails | Correct approach |
|---|---|---|---|
| 111. Minimum Depth | 1 + min(left, right) | The absent child returns 0 and wins the min, so a one-child node reports depth 1 | Handle the one-child case explicitly; better, BFS and stop at the first leaf |
| 222. Count Complete Tree Nodes | Traverse and count | Correct output, wrong complexity — the word "complete" is the whole problem | Compare spine heights, discard a perfect half in O(1) → O(log²n) |
| 543. Diameter | Return the diameter from dfs | A parent cannot extend a path that already bent | Return the height, record left + right on the side |
| 863. All Nodes Distance K | DFS down from the target | Distance also runs upward through the parent | Parent map, then BFS with visited |
| 987. Vertical Order Traversal | BFS and bucket by column | Traversal order does not order equal (row, col) nodes | Collect (col, row, val) triples and sort by all three |
| 98. Validate BST | Compare each node with its parent | The constraint is against every ancestor | Inherit (low, high) bounds, or check that inorder strictly increases |
| 235 vs 236 (LCA) | Use the general algorithm on the BST | O(n) where O(h) was available, and it ignores the one fact you were given | Descend by comparison |
| 669. Trim a BST | Return null for an out-of-range node | Its surviving subtree is discarded with it | Return the trimmed subtree from the side that can still be in range |
| 297. Serialize | Inorder, or preorder without markers | Neither is uniquely decodable | Preorder with # markers and one shared read cursor |
5 — MASTERY CHECKPOINTS#
Each gate is pass/fail, no partial credit. Gate conditions are things you do without an IDE, without hints, and without looking at your own notes. A gate you "mostly" pass is a gate you failed.
5.1 Traversal#
| Gate | You may advance when you can... | Fail action |
|---|---|---|
| A → B | Write all three recursive orders from one skeleton and state, in one sentence, why postorder is the only order that can compute a subtree aggregate. | Redo #1–#3 in a single sitting. |
| B → C | Write iterative inorder blind and state the stack invariant. Then write LC 173 and explain why next() is amortized O(1). | Redo #5, then #7. Hand-trace the stack on a 5-node tree. |
| C → D | Write the level-order skeleton blind, including the size snapshot and the null-root guard, and explain why LC 111 breaks the naive recursion. | Redo #9 and #10 together; the pair is the lesson. |
| D → E | Write LC 199 both ways — BFS last-of-level and right-first DFS — and say which is O(h) and which is O(w). | Redo #12. |
| E → F | State the heap-index rule and why per-level normalization is required, then explain the third sort key in LC 987 without looking. | Redo #17, then #18. |
| F → G | Given a new problem mentioning distance in a tree, say "parent map + BFS + visited" before writing code, and explain why the visited set is mandatory. | This is the most transferable gate in the pattern. Redo #20, then solve #21 cold. |
| G → H | Write Morris inorder blind, including the undo, and prove the tree is unmodified at the end. | Redo #23 daily until the undo is reflexive. |
| H → done | Generalize any of A–D to a child list without re-deriving, and state the identity element for the aggregate. | Redo #24 and #25. |
5.2 Tree Recursion#
| Gate | You may advance when you can... | Fail action |
|---|---|---|
| A → B | Answer the three questions (return / null / recorded-or-returned) out loud for LC 104, and write LC 110's sentinel version explaining the complexity difference. | Redo #27, #28. |
| B → C | Write the two-tree base case blind and explain why the crossed pairing in LC 101 is a parameter and not a different algorithm. | Redo #31, #32. |
| C → D | State the record/return distinction for LC 543 unprompted, then write LC 124 with the clamp and justify it on an all-negative tree. | You have the code but not the pattern. Re-derive both on paper before touching another problem. |
| D → E | Write LC 1448 blind and explain why sub-variant D needs no backtracking while E does. | Redo #40. |
| E → F | Write LC 113 blind with exactly one removeLast per addLast and the copy-on-record, and state the leaf condition without hesitating. | Redo #43, #44, #45 in that order. |
| F → G | Explain LC 437 as LC 560 transplanted onto the root path, including why the map entry must be decremented. | If the transfer isn't obvious, re-read the prefix-sum section of the companion document, then redo #47. |
| G → H | Write LC 236 blind and defend the "both sides non-null ⇒ this node" step, including the ancestor-of-the-other case. | Redo #48. |
| H → I | Write LC 105 blind and then LC 106 immediately after, and state the one difference between them from memory. | Redo both, back to back, two days running. |
| I → J | Explain why preorder needs null markers and inorder cannot work at all, then write serialize/deserialize with one shared cursor. | Redo #55. |
| J → K | Write LC 114's O(1)-space version and LC 117's dummy-head loop blind. | Redo #59, then #60. |
| K → L | Design the state tuple for LC 968 from scratch — three states, the transition, and the null value — without recalling the code. | This is the hardest gate in the document. Redo #63, #64, #65 in order across three days. |
| L → done | Derive ans[c] = ans[p] + n - 2 * size[c] on a blank page and say what each term counts. | Redo #67. If the derivation fails, the problem is not the problem — draw a 5-node tree and move the root by hand. |
5.3 Binary Search Trees#
| Gate | You may advance when you can... | Fail action |
|---|---|---|
| A → B | Write iterative search and BST-LCA blind, and state what the ordering bought you in each. | Redo #69, #70. |
| B → C | Write LC 98 both ways — inherited bounds and inorder-prev — and explain why Integer.MIN_VALUE sentinels are a bug. | This is the foundation gate. Do not proceed. Rewrite both until they are muscle memory. |
| C → D | State "the minimum difference is between inorder-adjacent nodes" unprompted, and describe LC 99's two-inversion rule from memory. | Redo #75, then #76. |
| D → E | Write successor blind and explain why the answer is the last left-turn rather than the node you stopped on. | Redo #79 and hand-trace it on a tree where the target has no right child. |
| E → F | Write LC 450 blind with all three cases and justify the recursive delete of the successor rather than a pointer splice. | Redo #81, then #82 daily until the two-child case is instant. |
| F → G | Write LC 108 blind, then explain LC 1008's O(n) solution as the LC 98 bound trick running forward. | Redo #83, #84. |
| G → H | Explain why LC 669 must return a subtree rather than null, with a concrete 4-node counterexample. | Redo #89. |
| H → done | Solve LC 653 with two iterators rather than a hash set, and name the two-pointer sub-variant it corresponds to. | You are treating BSTs as a topic rather than a tool. Redo #91, then read §3.1 again. |
5.4 Revisit rule for ★ problems#
Log every starred problem with an outcome the moment you finish it. The interval depends only on how you solved it, never on how you felt about it.
| Outcome | Next revisit | Then | Then | Graduates when |
|---|---|---|---|---|
| Clean — unaided, optimal, first submission accepted, ≤ 25 min | +14 days | +45 days | done | 2 consecutive clean runs |
| Slow — unaided and optimal, but > 40 min or multiple failed submissions | +7 days | +21 days | +45 days | 2 consecutive clean runs |
| Hinted — you read a hint, a tag, or the pattern name | +3 days | +10 days | +30 days | 2 consecutive clean runs (slow doesn't count) |
| Solved — you read the editorial or any solution code | +1 day | +4 days | +12 days | 3 consecutive clean runs |
| Suboptimal — accepted but wrong complexity | Treat as Hinted, and additionally re-solve the previous starred problem in the same sub-variant |
Additional rules that matter more than the intervals:
- Three questions first. On every revisit of a Pattern 2 problem, answer what does
dfsreturn / what is thenullvalue / is the answer returned or recorded before opening the editor. Getting those wrong downgrades the attempt to Hinted regardless of how the code goes. - Two strikes → step back. Any starred problem that fails to reach Clean on two consecutive revisits: stop, go back one sub-variant, and re-solve its last two starred problems. The failure is almost always upstream.
- Failure-mode tagging. When a revisit isn't clean, tag it with the row number from the relevant §*.4 Failure Modes table. After ten problems you will have two or three dominant tags — those are your actual weaknesses, and they're worth more than any problem count.
- The sub-variant transfer test. Once per sub-variant, take an unseen problem from the Extra Reps list and solve it cold. If the core problems are clean but the transfer fails, you learned the problems, not the pattern.
- Draw the tree. Any tree bug that survives two readings of the code gets a hand-drawn 5-to-7-node counterexample. Trees are the one topic where the drawing finds the bug faster than the debugger, every time.
- Never revisit an unstarred problem unless it's serving as a transfer test. Optional problems have no spaced-repetition schedule; that is what makes them optional.
- Cap the queue at 12 due items. If more than 12 come due, do the oldest 12 and push the rest. A backlog you avoid is worse than an interval you stretch.
Appendix — Coverage summary#
| Pattern | Sub-variants | ★ core | ⚠︎ anti-pattern | ○ optional |
|---|---|---|---|---|
| Traversal | 8 | 14 | 3 (LC 111, 987, 863) | 9 |
| Tree Recursion | 12 | 24 | 2 (LC 222, 543) | 16 |
| Binary Search Trees | 8 | 14 | 1 (LC 98) | 10 |
| Total | 28 | 52 | 6 | 35 |
The six ⚠︎ problems are the highest-value items in the document. They are the only ones that teach you when not to trust the obvious recursion, which is the difference between someone who has done 300 tree problems and someone who can solve an unseen one.
Where this document connects to the others. LC 437 is LC 560 on a root path. LC 653 is LC 167 on two iterators. LC 220 is an ordered-multiset sliding window that happens to use a BST. LC 230 and LC 2476 are binary search with pointers instead of indices. If those four sentences read as obvious, the patterns have transferred; if any of them reads as a surprise, that is the next thing to study.