Maximum Depth of a Binary Tree
Depth is defined in terms of itself: a node's depth is 1 plus the deeper of its two children. That makes recursion the natural fit — each call waits on its children, and the answer climbs back up the call stack.
Details
Animated on: Return the number of nodes along the longest path from the root down to the farthest leaf, for the tree [3, 9, 20, null, null, 15, 7].
Problem:Maximum Depth of Binary TreeEasy
Pattern:Tree DFS
Binary Trees
step 1 / 12
9
3
15
20
7
Call stack
maxDepth(3)
Call maxDepth(3). To answer for the root we first need the depths of its two children — so we go down before we can come back up.
Pseudocode
1FUNCTION maxDepth(node):2 IF node is null: RETURN 03 left = maxDepth(node.left)4 right = maxDepth(node.right)5 RETURN 1 + the larger of left and right6END FUNCTION
← / → step · space play · Home restart
Every step in words
Show all 12 steps
- Call maxDepth(3). To answer for the root we first need the depths of its two children — so we go down before we can come back up.
- Recurse into the left child, 9. The call to maxDepth(3) is paused on the stack, waiting for this to return.
- Node 9 has no children. Both maxDepth(null) calls hit the base case and return 0.
- So 9 returns 1 + max(0, 0) = 1. That value is now fixed for node 9, and its frame pops off the stack.
- Back inside maxDepth(3), the left result is 1. Now recurse into the right child, 20.
- 20 recurses into its left child, 15.
- 15 is a leaf — both children return 0 — so it returns 1 and pops.
- 20 recurses into its right child, 7.
- 7 is also a leaf → returns 1 and pops.
- Now 20 has both results: max(15 → 1, 7 → 1) = 1, so 20 returns 1 + 1 = 2.
- The root finally has both: max(9 → 1, 20 → 2) = 2, so 3 returns 1 + 2 = 3.
- Maximum depth = 3 (path 3 → 20 → 15 or 3 → 20 → 7). Every node was visited exactly once, so the whole tree costs O(n).
Now solve it yourself
Watching is the first half. The second is writing it without the animation.