IntermediateTrees
Thinking recursively about trees
Ask: if my children already had their answers, how do I build mine? Then add the base case for an empty tree.
The idea
Most tree problems are “combine the answers of the two subtrees”. Trust the recursive call to solve each subtree, and only write how to combine them plus what an empty tree returns.
Max depth: an empty tree has depth 0; otherwise it's 1 + the deeper child.
Worked example
Depth of a tree with root 3, children 9 and 20, and 20's children 15 and 7
- depth(9) = 1 + max(0, 0) = 1
- depth(15) = depth(7) = 1 → depth(20) = 1 + 1 = 2
- depth(3) = 1 + max(1, 2) = 3
In code (Python)
def max_depth(root):
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
def invert(root):
if root:
root.left, root.right = invert(root.right), invert(root.left)
return rootO(n) time, O(h) stack space for height h.
How to spot it
- Almost every binary tree question: depth, balance, same tree, paths, invert.
Common mistakes
- Forgetting the empty-tree base case.
- Trying to trace the whole recursion in your head; trust the subcalls.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →