Maximum Depth of Binary Tree
Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from root to leaf).
Why this is worth learning
Depth counts nodes on a longest root-to-leaf path. The empty-tree base case zero makes a leaf's depth emerge naturally as one.
Before coding: one-minute experiment
What are the depths of an empty tree, a leaf, and a four-node chain?
Function signature
func MaxDepth(root *TreeNode) int
Inputs / outputs
root: pointer to the root node.- Return: maximum depth.
Example
3
/ \
9 20
/ \
15 7
Output: 3
Constraints
- 0 <= number of nodes <= 100_000
Core idea (near-solution)
A direct method enumerates root-to-leaf paths and keeps the longest length, but the parent does not need the paths themselves. A child can return just the deepest length in its subtree. Every nonempty path from the parent takes the parent plus one child's route, so choose the larger child answer and add one. An empty subtree returns zero because the metric counts nodes. This meaning derives both the recurrence and the base case; a leaf then returns 1 without a separate special case.
Invariant: recursion returns correct depth for each subtree.
Algorithm (step-by-step)
- If node is nil, return 0.
- Recursively compute left and right depths.
- Return 1 + max(left, right).
Correctness sketch
For an empty tree, no path contains a node and depth is zero. Assume the recursive calls return the correct depths of the left and right subtrees. Any root-to-leaf path in the current tree starts with the root and then lies wholly in one child subtree. Its maximum possible length is therefore one plus the larger child depth. Returning that quantity is correct by structural induction. Every real node is processed once. The longest chain of unfinished calls follows one root-to-leaf path, giving O(h) stack usage rather than constant space.
Trace (hand walkthrough)
Example input:
3
/ \
9 20
/ \
15 7
Output: 3
Walk:
- leaf 9 has depth 1; leaves 15 and 7 have depth 1
- node 20 depth = 1 + max(1,1) = 2
- root 3 depth = 1 + max(1,2) = 3
Pitfalls to avoid
- Forgetting the base case for nil.
Debugging lens
Test a skewed chain, not only balanced trees. Recursive space is O(n) on a chain even though a balanced tree has height O(log n).
Complexity
- Time:
O(n) - Extra space:
O(h)recursion stack.
Implementation notes (Go)
- Handle
root == nilearly. - DFS recursion is simplest; BFS works if stack depth is a concern.
Reconstruction checkpoint
A root has a left leaf and a right chain of three nodes below the root. Predict the returned depth. How would the recurrence and empty-tree convention change if depth counted edges instead of nodes?
Model answer
The node-count depth is 4: the children return 1 and 3, and the root returns 1+max(1,3). For an edge-count definition with a leaf at 0, using nil depth −1 preserves the same 1+max recurrence; the empty tree then needs that explicitly chosen convention. A unit change requires revisiting base cases.