Minimum Depth of a Binary Tree: Why BFS Beats DFS Here

"Minimum Depth of Binary Tree" is a Easy-level staple in Amazon, Meta, Google loops, and it is a textbook fit for the Tree BFS pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 5 of 11 in the Tree BFS arc.

The Problem

Return the minimum depth: the number of nodes on the shortest path from the root to the nearest leaf. Two traps: a one-child node is not a leaf (the classic misread), and DFS must visit the whole tree while BFS can stop at the first leaf it meets.

Input:  root = [3, 9, 20, None, None, 15, 7]
Output: 2
For [2, None, 3, None, 4] the answer is 3 — node 2 is not a leaf.

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Nearest-anything in an unweighted structure is BFS's home turf: levels are explored in distance order, so the first leaf encountered is provably the shallowest. On a deep tree with an early leaf, that early exit is the difference between O(n) and O(first-leaf).

The Approach

Track depth per level with the snapshot loop; return the current depth the moment a popped node has no children. Nothing below that level can be shallower — the invariant that justifies stopping.

State the leaf definition before coding: min(depth(left), depth(right)) DFS breaks on one-child nodes (it counts a missing child as depth 0) and is the known wrong answer interviewers listen for.

Python Solution

class TreeNode:
    def __init__(self, val: int = 0, left: "TreeNode | None" = None,
                 right: "TreeNode | None" = None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque


def min_depth(root: TreeNode | None) -> int:
    """Nodes on the shortest root-to-leaf path."""
    if not root:
        return 0
    queue: deque[tuple[TreeNode, int]] = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth                   # first leaf is the nearest leaf
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
    return 0                               # unreachable for non-empty trees

Complexity

• Time: O(n) worst case — early exit at the shallowest leaf; degenerate trees still cost O(n)
• Space: O(w) — queue of (node, depth) pairs

Interview Tips and Follow-Ups

• Skewed-tree inputs like [2, None, 3, None, 4] exist purely to catch the min-of-children DFS bug — bring the counterexample up yourself.
• Storing depth in the queue tuple vs counting levels are equivalent; the tuple version survives refactoring to graph BFS better.
• Contrast with Maximum Depth (DFS arc): max requires full traversal, min rewards early exit — a crisp BFS-vs-DFS decision story.

That wraps part 5 of the Tree BFS arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.