Maximum Depth of Binary Tree (LeetCode 104)
You're handed the root of a binary tree and asked how tall it is: its maximum depth.
The maximum depth counts the nodes on the single longest chain running from the root all the way down to whichever leaf sits farthest away.
Worked Examples
root = [3,9,20,null,null,15,7]3root = [1,null,2]2⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 104].-100 <= Node.val <= 100
Core Insight
Tree problems naturally decompose into identical subproblems on the left and right subtrees.
Real-World Scenario & Production Applications
Directory tree depth calculation in filesystems, DOM tree depth traversal in browser rendering engines.
Step-by-Step Execution Trace Table
| Step | Call Frame | Depth | Action | Child Subtree Returns | Combine Step (max(L, R) + 1) | Value Returned Upward |
|---|---|---|---|---|---|---|
| 1 | Node 3 | d=1 | ⬇️ ENTER | Suspends; waits for children | — | — |
| 2 | Node 9 | d=2 | ⬇️ ENTER | Descends into left child | — | — |
| 3 | 9.left | d=3 | ⬇️↑ BASE | node is None | Base case: empty contributes 0 | 0 |
| 4 | 9.right | d=3 | ⬇️↑ BASE | node is None | Base case: empty contributes 0 | 0 |
| 5 | Node 9 | d=2 | ↑ COMBINE & RETURN | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 3) |
| 6 | Node 20 | d=2 | ⬇️ ENTER | Descends into right subtree | — | — |
| 7 | Node 15 | d=3 | ⬇️↑ LEAF | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 20) |
| 8 | Node 7 | d=3 | ⬇️↑ LEAF | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 20) |
| 9 | Node 20 | d=2 | ↑ COMBINE & RETURN | L=1, R=1 | max(1, 1) + 1 | 2 (to Node 3) |
| 10 | Node 3 | d=1 | ↑ COMBINE & FINISH | L=1, R=2 | max(1, 2) + 1 | 3 (Final Answer) |
root = [3,9,20,null,null,15,7]3| Step | Call Frame | Depth | Action | Child Subtree Returns | Combine Step (max(L, R) + 1) | Value Returned Upward |
|---|---|---|---|---|---|---|
| 1 | Node 3 | d=1 | ⬇️ ENTER | Suspends; waits for children | — | — |
| 2 | Node 9 | d=2 | ⬇️ ENTER | Descends into left child | — | — |
| 3 | 9.left | d=3 | ⬇️↑ BASE | node is None | Base case: empty contributes 0 | 0 |
| 4 | 9.right | d=3 | ⬇️↑ BASE | node is None | Base case: empty contributes 0 | 0 |
| 5 | Node 9 | d=2 | ↑ COMBINE & RETURN | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 3) |
| 6 | Node 20 | d=2 | ⬇️ ENTER | Descends into right subtree | — | — |
| 7 | Node 15 | d=3 | ⬇️↑ LEAF | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 20) |
| 8 | Node 7 | d=3 | ⬇️↑ LEAF | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 20) |
| 9 | Node 20 | d=2 | ↑ COMBINE & RETURN | L=1, R=1 | max(1, 1) + 1 | 2 (to Node 3) |
| 10 | Node 3 | d=1 | ↑ COMBINE & FINISH | L=1, R=2 | max(1, 2) + 1 | 3 (Final Answer) |
| 1 | if not root: |
| 2 | return 0 |
| 3 | left_depth = maxDepth(root.left) |
| 4 | right_depth = maxDepth(root.right) |
| 5 | return 1 + max(left_depth, right_depth) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Recursion asking a function to call itself feels circular the first time you see it — the trick is learning to trust it instead of trying to trace every call by hand.
🕵️ The Analogy: Sending Two Explorers and Waiting at the Door
Imagine you're standing at a node, and you need to know how deep the tree goes beneath you. You send one explorer down the left branch and one down the right branch, each with the exact same instructions: "go as deep as you can, then report back your depth." You don't follow them, and you don't need to know how they get their answer — you just wait at your own door. When they both report back, you take whichever explorer went deeper, add 1 for the step it took to reach you, and report that number to whoever sent you.
🔑 The Key Idea in the Code
"Trusting the recursion" means never asking how maxDepth(root.left) computed its answer — only that it did, correctly, for a strictly smaller tree. Every node in the tree plays the exact same "send two explorers, wait, combine" role, all the way down to the base case (None reports back 0, since an empty subtree has no depth to add).
Null child evaluation: Checking
if not root.left and not root.rightwithout handlingif not root: return 0first causes null dereference on empty inputs.Off-by-one on the combine step: Returning
max(left_depth, right_depth)without the+ 1for the current node undercounts depth at every level; the current node's own contribution must always be added on the way back up.Confusing 0-indexed height with 1-indexed depth: Depth is 1-indexed (single node has depth 1), whereas some tree definitions treat the root as height 0.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for the number of nodes on the longest root-to-leaf path: a value a node can compute from its two subtrees' answers, the Bottom-Up DFS signal.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
max_depth(root) returns 1 + max(left_depth, right_depth), where left_depth = max_depth(root.left) and right_depth = max_depth(root.right); an empty subtree returns 0.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: the base case
if not root: return 0must be the value1 + max(...)expects from an empty subtree.Depth counts nodes, not edges: a single node has depth 1, so returning
-1for an empty subtree (the edge-count convention) is off by one here.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Bottom-Up DFS. A node's depth depends only on its two subtrees, so I ask each child for its depth first and add one for the node itself on the way back up. Every call returns a finished answer for its own subtree, so the parent never looks deeper than those two numbers, and each node is visited exactly once. The one thing to get right is the base case: an empty subtree returns 0, which is exactly what one plus the max expects, so a leaf comes out as 1. If I returned minus one there, I'd be counting edges instead of nodes. That's
O(N)time and O(H) for the recursion stack, where H is the height. The tree can have ten thousand nodes, and a chain that deep is past Python's default recursion limit, so in Python I'd switch to an explicit stack or raise the limit.
Complexity & Mathematical Proof
O(N)
Look at the recursive function: def max_depth(root):. For every node in the binary tree, the function executes exactly 2 recursive calls (max_depth(root.left) and max_depth(root.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left_depth, right_depth)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) recursion stack
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local node pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = T(N_left) + T(N_right) + O(1) = O(N)
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
O(1) Work Per Frame1 + max(left_depth, right_depth)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = T(N_left) + T(N_right) + O(1) = O(N)
One O(1) frame per node and one per empty child (N + 1 of them), so 2N + 1 calls on any shape: a chain and a balanced tree of the same size cost the same.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximum depth of binary tree", "number of nodes along longest path from root to leaf". A node's answer comes only from its two subtrees' answers: Bottom-Up DFS, with no global state to share between calls.
. Time budget is strictly visiting each node once. Space budget is stack frames ( on balanced trees, worst-case on degenerate lists).
A chain of nodes, the LeetCode maximum, is already past CPython's default recursion limit of 1000: raise the limit, or walk with an explicit stack (or level by level with a queue).
Maximum Depth of Binary Tree (LeetCode 104)
You're handed the root of a binary tree and asked how tall it is: its maximum depth.
The maximum depth counts the nodes on the single longest chain running from the root all the way down to whichever leaf sits farthest away.
Worked Examples
root = [3,9,20,null,null,15,7]3root = [1,null,2]2⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 104].-100 <= Node.val <= 100
Core Insight
Tree problems naturally decompose into identical subproblems on the left and right subtrees.
Real-World Scenario & Production Applications
Directory tree depth calculation in filesystems, DOM tree depth traversal in browser rendering engines.
Step-by-Step Execution Trace Table
| Step | Call Frame | Depth | Action | Child Subtree Returns | Combine Step (max(L, R) + 1) | Value Returned Upward |
|---|---|---|---|---|---|---|
| 1 | Node 3 | d=1 | ⬇️ ENTER | Suspends; waits for children | — | — |
| 2 | Node 9 | d=2 | ⬇️ ENTER | Descends into left child | — | — |
| 3 | 9.left | d=3 | ⬇️↑ BASE | node is None | Base case: empty contributes 0 | 0 |
| 4 | 9.right | d=3 | ⬇️↑ BASE | node is None | Base case: empty contributes 0 | 0 |
| 5 | Node 9 | d=2 | ↑ COMBINE & RETURN | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 3) |
| 6 | Node 20 | d=2 | ⬇️ ENTER | Descends into right subtree | — | — |
| 7 | Node 15 | d=3 | ⬇️↑ LEAF | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 20) |
| 8 | Node 7 | d=3 | ⬇️↑ LEAF | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 20) |
| 9 | Node 20 | d=2 | ↑ COMBINE & RETURN | L=1, R=1 | max(1, 1) + 1 | 2 (to Node 3) |
| 10 | Node 3 | d=1 | ↑ COMBINE & FINISH | L=1, R=2 | max(1, 2) + 1 | 3 (Final Answer) |
root = [3,9,20,null,null,15,7]3| Step | Call Frame | Depth | Action | Child Subtree Returns | Combine Step (max(L, R) + 1) | Value Returned Upward |
|---|---|---|---|---|---|---|
| 1 | Node 3 | d=1 | ⬇️ ENTER | Suspends; waits for children | — | — |
| 2 | Node 9 | d=2 | ⬇️ ENTER | Descends into left child | — | — |
| 3 | 9.left | d=3 | ⬇️↑ BASE | node is None | Base case: empty contributes 0 | 0 |
| 4 | 9.right | d=3 | ⬇️↑ BASE | node is None | Base case: empty contributes 0 | 0 |
| 5 | Node 9 | d=2 | ↑ COMBINE & RETURN | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 3) |
| 6 | Node 20 | d=2 | ⬇️ ENTER | Descends into right subtree | — | — |
| 7 | Node 15 | d=3 | ⬇️↑ LEAF | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 20) |
| 8 | Node 7 | d=3 | ⬇️↑ LEAF | L=0, R=0 | max(0, 0) + 1 | 1 (to Node 20) |
| 9 | Node 20 | d=2 | ↑ COMBINE & RETURN | L=1, R=1 | max(1, 1) + 1 | 2 (to Node 3) |
| 10 | Node 3 | d=1 | ↑ COMBINE & FINISH | L=1, R=2 | max(1, 2) + 1 | 3 (Final Answer) |
| 1 | if not root: |
| 2 | return 0 |
| 3 | left_depth = maxDepth(root.left) |
| 4 | right_depth = maxDepth(root.right) |
| 5 | return 1 + max(left_depth, right_depth) |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Recursion asking a function to call itself feels circular the first time you see it — the trick is learning to trust it instead of trying to trace every call by hand.
🕵️ The Analogy: Sending Two Explorers and Waiting at the Door
Imagine you're standing at a node, and you need to know how deep the tree goes beneath you. You send one explorer down the left branch and one down the right branch, each with the exact same instructions: "go as deep as you can, then report back your depth." You don't follow them, and you don't need to know how they get their answer — you just wait at your own door. When they both report back, you take whichever explorer went deeper, add 1 for the step it took to reach you, and report that number to whoever sent you.
🔑 The Key Idea in the Code
"Trusting the recursion" means never asking how maxDepth(root.left) computed its answer — only that it did, correctly, for a strictly smaller tree. Every node in the tree plays the exact same "send two explorers, wait, combine" role, all the way down to the base case (None reports back 0, since an empty subtree has no depth to add).
Null child evaluation: Checking
if not root.left and not root.rightwithout handlingif not root: return 0first causes null dereference on empty inputs.Off-by-one on the combine step: Returning
max(left_depth, right_depth)without the+ 1for the current node undercounts depth at every level; the current node's own contribution must always be added on the way back up.Confusing 0-indexed height with 1-indexed depth: Depth is 1-indexed (single node has depth 1), whereas some tree definitions treat the root as height 0.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for the number of nodes on the longest root-to-leaf path: a value a node can compute from its two subtrees' answers, the Bottom-Up DFS signal.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
max_depth(root) returns 1 + max(left_depth, right_depth), where left_depth = max_depth(root.left) and right_depth = max_depth(root.right); an empty subtree returns 0.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: the base case
if not root: return 0must be the value1 + max(...)expects from an empty subtree.Depth counts nodes, not edges: a single node has depth 1, so returning
-1for an empty subtree (the edge-count convention) is off by one here.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Bottom-Up DFS. A node's depth depends only on its two subtrees, so I ask each child for its depth first and add one for the node itself on the way back up. Every call returns a finished answer for its own subtree, so the parent never looks deeper than those two numbers, and each node is visited exactly once. The one thing to get right is the base case: an empty subtree returns 0, which is exactly what one plus the max expects, so a leaf comes out as 1. If I returned minus one there, I'd be counting edges instead of nodes. That's
O(N)time and O(H) for the recursion stack, where H is the height. The tree can have ten thousand nodes, and a chain that deep is past Python's default recursion limit, so in Python I'd switch to an explicit stack or raise the limit.
Complexity & Mathematical Proof
O(N)
Look at the recursive function: def max_depth(root):. For every node in the binary tree, the function executes exactly 2 recursive calls (max_depth(root.left) and max_depth(root.right)) and performs O(1) constant-time arithmetic combining their results (1 + max(left_depth, right_depth)). Because each of the N tree nodes is visited and processed exactly once, total time is N · O(1) = O(N).
O(H) recursion stack
Look at the recursion call stack: Each recursive call adds a new stack frame storing the local node pointer. The maximum number of simultaneous stack frames alive at any instant equals the maximum path depth from root to leaf, which is the tree height H. In a balanced binary tree, H = log2(N) -> O(log N) stack memory. In a worst-case skewed tree (linked list), H = N -> O(N) stack memory. We allocate zero heap objects, so auxiliary space is bounded by tree height O(H).
T(N) = T(N_left) + T(N_right) + O(1) = O(N)
Derivation Progression
N nodes visited
Every node in the binary tree is entered and exited exactly once.
O(1) Work Per Frame1 + max(left_depth, right_depth)
Combining child subproblem depths requires a single addition and max comparison in O(1).
T(N) = T(N_left) + T(N_right) + O(1) = O(N)
One O(1) frame per node and one per empty child (N + 1 of them), so 2N + 1 calls on any shape: a chain and a balanced tree of the same size cost the same.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Recursion stack storing tree height H frames (O(log N) balanced, O(N) skewed)
O(1) Zero heap allocations
O(1) Returns integer tree depth
Boundary Best / Worst Cases
time with stack on balanced tree.
time with stack.
time with stack on skewed tree (linked list shape).
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "maximum depth of binary tree", "number of nodes along longest path from root to leaf". A node's answer comes only from its two subtrees' answers: Bottom-Up DFS, with no global state to share between calls.
. Time budget is strictly visiting each node once. Space budget is stack frames ( on balanced trees, worst-case on degenerate lists).
A chain of nodes, the LeetCode maximum, is already past CPython's default recursion limit of 1000: raise the limit, or walk with an explicit stack (or level by level with a queue).