Minimum Depth of Binary Tree (LeetCode 111)
Given a binary tree, compute its minimum depth — the node count along the shortest root-to-leaf path.
Minimum depth means the fewest nodes you must pass through, starting at the root, to reach any leaf.
Note: a leaf has no children at all.
Worked Examples
root = [3,9,20,null,null,15,7]23 -> 9, which has 2 nodes.root = [2,null,3,null,4,null,5,null,6]52 -> 3 -> 4 -> 5 -> 6, so its only leaf is 5 nodes down.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 105].-1000 <= Node.val <= 1000
Core Insight
BFS level-by-level exploration guarantees that the first leaf encountered has minimal depth.
Real-World Scenario & Production Applications
Finding closest exit in navigation graphs, game-tree fastest win detection.
Subproblems & Recurrence Decomposition3 Phases
Seed queue with (root, 1) representing the current node and its depth level. If not root, return 0 immediately.
if not root:
return 0
queue = deque([(root, 1)])Step-by-Step Execution Trace Table
Step-by-Step Wavefront Progression
- Step 1 (Root Seed, Depth 1, d=1):
queue = [(3, 1)]. Push root with initial depth 1. - Step 2 (Dequeue 3, Non-Leaf, d=1): Pop
(3, 1). Node 3 has children9and20(not a leaf). Enqueue(9, 2)and(20, 2)queue = [(9, 2), (20, 2)]. - Step 3 (Dequeue 9, Leaf Encountered, Early Exit, d=2): Pop
(9, 2). Node 9 hasleft is Noneandright is None. First Leaf Hit: Immediately terminate BFS and return minimal depth2✅.
root = [3,9,20,null,null,15,7]Expected:2| 1 | if not root: |
| 2 | return 0 |
| 3 | queue = deque([(root, 1)]) |
| 4 | while queue: |
| 5 | node, depth = queue.popleft() |
| 6 | if node is a leaf: |
| 7 | return depth |
| 8 | append the children of node to queue with depth + 1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
DFS can also find a tree's minimum depth — but it has to explore an entire skewed branch before it can be sure that branch isn't the shortest. BFS never has that problem.
🎯 The Analogy: A Search Party That Fans Out in Rings
Imagine a search party looking for the nearest exit from a maze, fanning outward in rings from the entrance — everyone one step away checks in before anyone two steps away even starts moving. The very first exit anyone reports back is guaranteed to be the closest one, because every exit at a smaller ring radius would have already been found and reported first. There's no need to keep searching once the first exit is found — every unexplored ring is, by definition, farther away.
🔑 The Key Idea in the Code
This early return is only safe because it's BFS, not DFS — a depth-first search could stumble onto a distant leaf down an early branch before ever checking a much closer leaf sitting on a different branch.
Single-child false leaf trap: A node with only one child is NOT a leaf. If a node has
left = Noneandright = Node(2), returning 1 becauseleft is Noneis wrong; min depth must reach a true leaf (left is None and right is None).Skewed tree DFS inefficiency: Using DFS on a skewed tree explores all nodes; BFS guarantees finding the minimum depth at first leaf discovery ( work).
Root level 0 vs 1 off-by-one: LeetCode defines single-node tree minimum depth as 1. Initializing
depth = 0and incrementing before leaf check ensures correct unit reporting.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Shortest path to any leaf in a tree.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: BFS explores by increasing depth; the first leaf dequeued is guaranteed to be at minimum depth.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use BFS with a queue storing (node, depth) pairs. I pop nodes in arrival order; the first node with no left and no right child triggers an immediate return of its depth. Runs in
O(N)time and O(W) space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: BFS explores level by level and returns depth immediately upon encountering the first leaf node (node with no children).
O(W) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Queue holds nodes at the current depth tier.
T(N) = O(K) ≤ O(N)
Derivation Progression
depth += 1 per level
Tracks current tier distance from root.
if not node.left and not node.right: return depth
Terminates immediately at shallowest leaf.
O(K) ≤ O(N)
Visits only nodes up to the first leaf level.
Variable Definitions
Total number of nodes in the binary tree
Number of nodes visited down to shallowest leaf
Memory Architecture & Bounds
O(1) Iterative
O(W) Queue up to min depth level width
O(1) Depth integer
Boundary Best / Worst Cases
if root is a leaf.
.
if all leaves are at the deepest level.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum depth of binary tree", "nearest leaf node". In contrast to DFS (which must traverse the full tree down to every leaf to find the minimum), BFS traverses level-by-level: The first leaf node encountered terminates the search immediately!
. Early exit terminates in where is the number of nodes at depths .
Empty root returns 0. Continuing search after discovering the first leaf: break immediately!
Minimum Depth of Binary Tree (LeetCode 111)
Given a binary tree, compute its minimum depth — the node count along the shortest root-to-leaf path.
Minimum depth means the fewest nodes you must pass through, starting at the root, to reach any leaf.
Note: a leaf has no children at all.
Worked Examples
root = [3,9,20,null,null,15,7]23 -> 9, which has 2 nodes.root = [2,null,3,null,4,null,5,null,6]52 -> 3 -> 4 -> 5 -> 6, so its only leaf is 5 nodes down.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 105].-1000 <= Node.val <= 1000
Core Insight
BFS level-by-level exploration guarantees that the first leaf encountered has minimal depth.
Real-World Scenario & Production Applications
Finding closest exit in navigation graphs, game-tree fastest win detection.
Subproblems & Recurrence Decomposition3 Phases
Seed queue with (root, 1) representing the current node and its depth level. If not root, return 0 immediately.
if not root:
return 0
queue = deque([(root, 1)])Step-by-Step Execution Trace Table
Step-by-Step Wavefront Progression
- Step 1 (Root Seed, Depth 1, d=1):
queue = [(3, 1)]. Push root with initial depth 1. - Step 2 (Dequeue 3, Non-Leaf, d=1): Pop
(3, 1). Node 3 has children9and20(not a leaf). Enqueue(9, 2)and(20, 2)queue = [(9, 2), (20, 2)]. - Step 3 (Dequeue 9, Leaf Encountered, Early Exit, d=2): Pop
(9, 2). Node 9 hasleft is Noneandright is None. First Leaf Hit: Immediately terminate BFS and return minimal depth2✅.
root = [3,9,20,null,null,15,7]Expected:2| 1 | if not root: |
| 2 | return 0 |
| 3 | queue = deque([(root, 1)]) |
| 4 | while queue: |
| 5 | node, depth = queue.popleft() |
| 6 | if node is a leaf: |
| 7 | return depth |
| 8 | append the children of node to queue with depth + 1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
DFS can also find a tree's minimum depth — but it has to explore an entire skewed branch before it can be sure that branch isn't the shortest. BFS never has that problem.
🎯 The Analogy: A Search Party That Fans Out in Rings
Imagine a search party looking for the nearest exit from a maze, fanning outward in rings from the entrance — everyone one step away checks in before anyone two steps away even starts moving. The very first exit anyone reports back is guaranteed to be the closest one, because every exit at a smaller ring radius would have already been found and reported first. There's no need to keep searching once the first exit is found — every unexplored ring is, by definition, farther away.
🔑 The Key Idea in the Code
This early return is only safe because it's BFS, not DFS — a depth-first search could stumble onto a distant leaf down an early branch before ever checking a much closer leaf sitting on a different branch.
Single-child false leaf trap: A node with only one child is NOT a leaf. If a node has
left = Noneandright = Node(2), returning 1 becauseleft is Noneis wrong; min depth must reach a true leaf (left is None and right is None).Skewed tree DFS inefficiency: Using DFS on a skewed tree explores all nodes; BFS guarantees finding the minimum depth at first leaf discovery ( work).
Root level 0 vs 1 off-by-one: LeetCode defines single-node tree minimum depth as 1. Initializing
depth = 0and incrementing before leaf check ensures correct unit reporting.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Shortest path to any leaf in a tree.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: BFS explores by increasing depth; the first leaf dequeued is guaranteed to be at minimum depth.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use BFS with a queue storing (node, depth) pairs. I pop nodes in arrival order; the first node with no left and no right child triggers an immediate return of its depth. Runs in
O(N)time and O(W) space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: BFS explores level by level and returns depth immediately upon encountering the first leaf node (node with no children).
O(W) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Queue holds nodes at the current depth tier.
T(N) = O(K) ≤ O(N)
Derivation Progression
depth += 1 per level
Tracks current tier distance from root.
if not node.left and not node.right: return depth
Terminates immediately at shallowest leaf.
O(K) ≤ O(N)
Visits only nodes up to the first leaf level.
Variable Definitions
Total number of nodes in the binary tree
Number of nodes visited down to shallowest leaf
Memory Architecture & Bounds
O(1) Iterative
O(W) Queue up to min depth level width
O(1) Depth integer
Boundary Best / Worst Cases
if root is a leaf.
.
if all leaves are at the deepest level.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "minimum depth of binary tree", "nearest leaf node". In contrast to DFS (which must traverse the full tree down to every leaf to find the minimum), BFS traverses level-by-level: The first leaf node encountered terminates the search immediately!
. Early exit terminates in where is the number of nodes at depths .
Empty root returns 0. Continuing search after discovering the first leaf: break immediately!