Tree Patterns
Trees are where recursion becomes natural rather than clever, because the structure is recursive and the code mirrors it. Most tree problems are one question asked twice: what do I need from my children, and what do I return to my parent. Getting into the habit of answering those two questions before writing anything solves a surprising proportion of the topic.
Where to start, and what comes next
- 01
Traversal
The four traversals, in-order especially, since on a BST it produces sorted output and that fact drives several later problems.
- 03
Path Problems
Path sums and diameters, where a node returns one value upward while updating a different global answer. That asymmetry catches people out.
- 04
BST Patterns
Validation, kth smallest and lowest common ancestor, all of which exploit the ordering rather than searching blindly.
- 05
Construction & Serialization
Building a tree from traversals and serialising it. Good for confirming you really understand what each traversal preserves.
If you only have time for three things
- Bottom-up recursion, where each call combines what its children returned. It needs no shared state and is usually the cleaner of the two directions.
- Validating a BST by carrying an allowed range down, rather than comparing each node to its own children, which passes on trees that are not BSTs.
- In-order traversal on a BST producing sorted values, which is the basis for kth smallest and for validation by comparison.
State the direction before you write. Saying whether information flows down as a constraint or up as a result tells the interviewer you have a plan, and it usually determines the whole solution. The classic trap here is validating a BST with only local comparisons, and interviewers use it specifically because the wrong answer looks correct on small examples.
The idea underneath
Tree problems are almost always DFS (recursion) or BFS (level-order). The pattern: solve for children, combine results, return up. BST's sorted property lets you prune half the tree.
Problems that use these patterns
Head to head
Questions people ask
What is the difference between top-down and bottom-up here?
Top-down passes information into the recursive call, such as the allowed range when validating a BST. Bottom-up returns information out of it, such as a subtree's depth. If a node needs context from its ancestors it is top-down; if it needs facts about its descendants it is bottom-up.
Why does comparing a node to its children fail for BST validation?
Because the property is not local. Every node in a right subtree must exceed the root, however deep it sits. A tree with 5 at the root, 7 on the right, and 3 under that 7 satisfies every parent-child comparison and is still not a BST.
How deep can tree recursion safely go?
A balanced tree is fine, since depth is logarithmic and a million nodes is about twenty frames. A degenerate tree that is effectively a linked list is the risk, and that is when an iterative traversal with an explicit stack becomes necessary.