FAANGPrep Sprint
Maximum Depth of Binary Tree
Find the maximum depth (height) of a binary tree.
Examples
The tree has nodes 3 -> (9, 20). 20 -> (15, 7). The longest path is 3->20->15 (length 3).
Problem Understanding
Return the maximum depth of the binary tree under root: how many nodes lie on the longest downward path from the root to any leaf, counting both the root and the leaf.
Algorithm Strategy (Bottom-Up)
We use Post-order DFS (Bottom-Up) to solve this.
- Base Case: If the node is
null, its depth is0. - Recursive Step:
- Ask the Left Child: "What is your max depth?"
- Ask the Right Child: "What is your max depth?"
- Calculation: My Depth =
max(left_depth, right_depth) + 1.
Interactive Visualization
→ N = THE DEPTH A NODE RETURNED
CALL
Stack depth
1
Max depth
—
call stack
maxDepth(3)
Next
Ask 3's left child for its depth
Tree
Legend & Complexity
The node whose call is running
Waiting for a child to return its depth
Returned: its depth is under it
Time
O(n)
Space
O(h) call stack
Each node asks its left child, then its right child, for a depth, and returns the larger plus one. A node’s returned depth appears under it only when it returns, so the numbers fill in from the leaves up; an empty child shows the 0 it returns.
Dry Run
| Node | Left Depth | Right Depth | Calculation | Return Value |
|---|---|---|---|---|
| 9 | 0 | 0 | max(0,0) + 1 | 1 |
| 15 | 0 | 0 | max(0,0) + 1 | 1 |
| 7 | 0 | 0 | max(0,0) + 1 | 1 |
| 20 | 1 (from 15) | 1 (from 7) | max(1,1) + 1 | 2 |
| 3 | 1 (from 9) | 2 (from 20) | max(1,2) + 1 | 3 |
Edge Cases
- Empty Tree (Root is null): Return 0.
- Single Node: Return 1.
- Skewed Tree: Effectively a linked list, depth = N.
Solution
Bottom-up in every language: ask the left side, ask the right side, return the larger + 1.
Maximum Depth of Binary Tree Code
1var maxDepth = function(root) {2 if (!root) return 0;3 const left = maxDepth(root.left);4 const right = maxDepth(root.right);5 return Math.max(left, right) + 1;6};