Minimum Depth of Binary Tree

Minimum Depth of Binary Tree asks for the shortest distance from the root to the nearest leaf. It is a clean lesson in choosing the right traversal: a breadth-first sweep finds the answer the instant it pops the first leaf, often without touching most of the tree.

The slow way first

The natural first instinct is depth-first recursion: the minimum depth of a node is 1 + min(left depth, right depth). That works, but it has a subtle trap and it always explores the entire tree. To find the shortest path you must walk every branch all the way down before you can compare them — even branches that are far deeper than the nearest leaf.

The question to ask: which leaf is closest to the root? If we could visit nodes strictly in order of how deep they are, the first leaf we meet would automatically be the closest one — and we could stop right there.

The idea: breadth-first, level by level

A breadth-first (level-order) traversal uses a queue and drains the tree one depth at a time: first the root, then everything at depth 2, then everything at depth 3, and so on. Tag each node with its depth as you enqueue it. The first leaf you dequeue is guaranteed to be at the shallowest depth, so its depth is the answer — and you stop immediately.

The key insight: because BFS never visits a deeper node before a shallower one, the first leaf it reaches cannot be beaten. That lets us return early instead of exploring the whole tree.

Walk through it

Step through the animation. The root 3 goes into the queue at depth 1. We pop it, see it has children, and enqueue 9 and 20 at depth 2. Next we pop 9 — it has no children, so it is a leaf at depth 2. We return 2 and never look at 15 or 7 down on depth 3.

Pseudocode

if the tree is empty:
    return 0
put (root, depth = 1) into a queue
while the queue is not empty:
    take (node, depth) from the FRONT of the queue
    if node has no left child and no right child:
        return depth          # first leaf popped = nearest leaf
    if node has a left child:  enqueue (left,  depth + 1)
    if node has a right child: enqueue (right, depth + 1)

The Python solution

from collections import deque
 
def min_depth(root):
    if root is None:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

• deque is a double-ended queue; popleft() pulls from the front in O(1), which is what makes this breadth-first.
• Each queue entry is a pair (node, depth) so every node carries its own level with it.
• Line 9 is the leaf test — a node with no left and no right child. The very first time it is true, we are at the shallowest leaf.
• Line 10 returns that depth immediately, so we never process the levels below it.
• We only enqueue children that actually exist, each tagged with depth + 1.

Complexity

In the worst case (a tree where the nearest leaf is at the bottom) we still touch every node, so the time is O(n). The space is O(n) for the queue, which at its widest can hold a whole level of the tree.

When this pattern shows up

Practice