Coding Interview PatternsMinimum Depth of Binary Tree
EasyTree Breadth-First Search

Minimum Depth of Binary Tree

Explanation & Solution

Practice Problem

Description

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Examples

Example 1:

```tree

[3, 9, 20, null, null, 15, 7]

`

Input:root = [3, 9, 20, null, null, 15, 7]
0
3
1
9
2
20
3
null
4
null
5
15
6
7

Output: 2

Explanation: The shortest path is 3 → 9, which has depth 2. Node 9 is a leaf.

Example 2:

```tree

[2, null, 3, null, 4, null, 5, null, 6]

`

Input:root = [2, null, 3, null, 4, null, 5, null, 6]
0
2
1
null
2
3
3
null
4
4
5
null
6
5
7
null
8
6

Output: 5

Explanation: The only leaf is node 6. The path 2 → 3 → 4 → 5 → 6 has depth 5.

Example 3:

Input: root = []

Output: 0

Constraints

  • The number of nodes in the tree is in the range [0, 10⁵]
  • -1000 <= Node.val <= 1000

Approach

Tree Breadth-First Search pattern

1. Handle Empty Tree

  • If root is null:
  • Return 0
  • An empty tree has depth 0

2. Initialize BFS

  • Create queue = [root] with head = 0 pointer
  • Create depth = 0 to track the current level

3. Process Level by Level

  • While the queue is not empty:
  • Calculate levelSize = queue.length - head
  • Increment depth by 1 for the new level

4. Check for Leaf Nodes

  • For each node in the current level:
  • Dequeue via queue[head++]
  • If the node is a leaf (no left and no right child):
  • Return depth immediately
  • Otherwise, enqueue its children

5. Why BFS is Optimal Here

  • BFS explores level by level
  • The first leaf encountered is guaranteed to be at the minimum depth
  • We can return immediately without exploring deeper levels
  • DFS would need to explore the entire tree to find the minimum

6. Early Termination

  • Unlike maximum depth, we don't need to visit all nodes
  • BFS finds the shallowest leaf in the fewest steps

Key Insight

  • BFS is ideal for minimum depth — it finds the nearest leaf first
  • A node with only one child is not a leaf, so we must keep going
Time
O(n) worst case, but often terminates early
Space
O(n)queue holds at most one level of nodes

Visualization

Input:
DFS Traversal[3, 9, 20, 15, 7]
3920157
output0

Press play to start DFS traversal

CurrentIn stackComplete
11 steps

Solution Code

Previous
Average of Levels in Binary Tree
Next
Binary Tree Level Order Traversal II