Find the maximum depth (height) of a binary tree.
The maximum depth is 1 plus the larger of the left and right subtree depths. A single recursive call naturally expresses this: at every node, ask both children for their depth and take the max. The base case is None, which returns 0.
How to think about it
Recognise the pattern
The signal is any question that asks about a property of a subtree that depends recursively on its children’s properties — depth, diameter, balance, path sum. These are post-order DFS problems: you need answers from both children before you can answer for the current node. If you can express the answer as f(node) = combine(f(node.left), f(node.right)), DFS is the tool.
Build the approach step by step
Brute force / iterative BFS would count the number of levels using level-order traversal. Correct, but more code than needed.
The recursive insight: the depth of a tree rooted at node is 1 + max(depth(left), depth(right)). The recursion bottoms out when node is None — an empty subtree has depth 0. This one-liner recurrence is all you need.
Walk through:
3
/ \
9 20
/ \
15 7depth(15)= 1 + max(0,0) = 1depth(7)= 1 + max(0,0) = 1depth(20)= 1 + max(1,1) = 2depth(9)= 1 + max(0,0) = 1depth(3)= 1 + max(1,2) = 3
Complexity
- Time — O(n): every node is visited exactly once.
- Space — O(h): the call stack depth equals the tree height h. Best case O(log n) for a balanced tree, O(n) for a skewed one (degenerate linked list).