Pattern 1: Recursive DFS
This is the pattern that solves most tree problems. The idea is counterintuitive at first: you do not traverse the tree "by hand" — you trust the recursion to solve the subtrees and only decide how to combine.
Try it first: Maximum Depth of Binary Tree
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
Return the maximum depth of a binary tree (number of nodes on the longest path from the root down to a leaf). The tree is given as root (each node has .val, .left, .right).
Example: [3,9,20,null,null,15,7] → 3. (For testing, we pass the tree in level order.)
Did you try? If you tried to traverse level by level counting, it works — but there is a much simpler and more direct way to think about it. The theory below shows the recursive "leap of faith".
The theory: the recursive leap of faith
Faced with a tree, instead of imagining all the nodes, ask three questions:
- Base case: what is the answer for the empty tree (
None)? (almost always the trivial one: 0,True,None...) - Leap of faith: assume the recursion has already given you the correct answer for the left subtree and for the right one.
- Combine: how do you build the current node's answer from those two answers?
This is the universal DFS template for trees:
def solve(node):
if node is None: → return the base case
left = solve(node.left) # leap of faith
right = solve(node.right) # leap of faith
return combine(node, left, right)
For Maximum Depth: base case None → 0; combination
1 + max(left, right). You never think about the whole tree — only about the
current node, trusting the children. Watch the DFS go all the way down and come
back combining (blue shows the nodes already visited, amber is where the
recursion is now):
Why is it O(n) time and O(h) space?
The function is called once per node (each node is the "node" of exactly one call) and does O(1) work to combine → O(n) time. The space is the depth of the recursion stack, which goes down to the height h: O(h) — log n if balanced, n in the worst case (remember the previous lesson).
The same template, other problems
By swapping only the combination and the base case, the template solves a whole family:
| Problem | Base case | Combine |
|---|---|---|
| Maximum depth | None → 0 | 1 + max(left, right) |
| Invert the tree | None → None | swap: node.left=right; node.right=left |
| Are they equal? (two trees) | both None → True | a.val==b.val AND left AND right |
| Sum of all values | None → 0 | node.val + left + right |
See invert and are they equal — notice that only the combine line changes:
The key shift
What separates those who struggle with trees from those who solve them: stop trying to "follow the pointers in your head" and start trusting the recursion. Define the base case, assume the children are solved, and focus only on the combination. That mental habit applies to trees, and later to graphs and DP.
🧠 Review quiz
0/41. What is the 'universal template' for recursive DFS on a tree?
2. For the maximum depth, what is the correct combination from the children's answers?
3. Why is recursive DFS on a tree O(n) time?
4. Inverting the tree and checking whether two trees are equal use the SAME template. What changes between them?
Summary
- Universal template: base case (None) → solve(left) → solve(right) → combine.
- "Leap of faith": trust that the recursion solves the children; focus on the combination.
- O(n) time, O(h) space (recursion stack).
- Depth, invert, equality, sum... all are the same template.
Next lesson: when the question is per level — BFS.