← Back to problems Solve on LeetCode → ◆ Tree Patterns See #104 Max Depth →

Minimum Depth of Binary Tree

BFS — Early Exit at First Leaf

LeetCode 111 • Easy • Trees

Input: root = [3, 9, 20, null, null, 15, 7] → Output: 2
The minimum depth is the shortest path from root to the nearest leaf node. BFS guarantees the first leaf found is the shallowest.

Time O(n) worst-case visits all nodes

Space O(n) queue holds widest level

Visited: 0/5 Queue: 0 Depth: 0

Processing

In Queue

Processed

Leaf Found!

Edge highlight

Queue

empty

Depth

Speed:

Ready

Press Play to watch BFS find the shallowest leaf, or Step to advance one operation at a time.
Unlike max depth, BFS returns immediately when it hits the first leaf — no need to traverse the entire tree.

✎ Whiteboard

Size: 3

⌨ Type It — Build Muscle Memory

Practice until you don't need to look. Use the guide comments below as scaffolding. Type the full implementation in the editor. The green highlights are the nuances to burn into memory.

# ─── MINIMUM DEPTH (LeetCode 111) ───

# Pattern: BFS + early exit at first leaf

# Time: O(n) Space: O(n)

# 1. Import: from collections import deque

# 2. Define: minDepth(self, root)

# Base case: if not root: return 0

# 3. Init data structures:

# queue = deque([root]) ← BFS queue starts with root

# depth = 0 ← counts levels processed

# 4. BFS loop: while queue:

# Snapshot level size: level_size = len(queue)

# KEY LINE: depth += 1 ← increment BEFORE processing

# 5. Process each node in level:

# for i in range(level_size):

# node = queue.popleft() ← O(1) dequeue

# 6. KEY DIFFERENCE vs Max Depth:

# if not node.left and not node.right:

# return depth ← EARLY EXIT at first leaf!

# 7. Enqueue children (only if not a leaf):

# if node.left: queue.append(node.left)

# if node.right: queue.append(node.right)

# Why BFS? First leaf found IS the shallowest — guaranteed.

# DFS would need to check ALL paths before knowing the minimum.

# Vars: queue (deque), depth (int), node

▼ your implementation ▼

Verify your solution:

⌨ Type It — Recursive DFS

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ MIN DEPTH — RECURSIVE DFS ═══

PATTERN ▸ Post-order DFS + single-child guard O(n) · O(h)

① BASE CASE

if not root: return 0

② SINGLE-CHILD GUARDS

if not root.left:

return 1 + self.minDepth(root.right)

if not root.right:

return 1 + self.minDepth(root.left)

③ BOTH CHILDREN → RECURSE

left = self.minDepth(root.left)

right = self.minDepth(root.right)

④ COMBINE

return 1 + min(left, right)

▼ your implementation ▼

Verify your solution: