Minimum Depth of Binary Tree

Interview Prep

Warm-upTrees Variation of Maximum Depth of Binary Treetreesrecursionbfs

The problem

Given the root of a binary tree, return its minimum depth — the length of the shortest root-to-leaf path. A leaf is a node with no children at all. An empty tree has depth 0.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Why this is harder than Max Depth

Max depth is a clean recurrence: 1 + max(depth(left), depth(right)). Naively swapping min for max looks like it should work — but it doesn't, because an absent child returns depth 0, and min(0, k) is always 0. The algorithm reports "depth 1" for any node that has only one child, even though the node isn't a leaf.

def min_depth_wrong(root):
    """WRONG — symmetric with max_depth, but breaks when one child is None."""
    if root is None: return 0
    return 1 + min(min_depth_wrong(root.left), min_depth_wrong(root.right))

# Tree:  1
#         \
#          2
# At node 1: left=None -> depth 0, right=Node(2).
# min(0, 1) = 0 -> total 1.   But 1 is NOT a leaf!  The real answer is 2.

The fix is to handle "one missing child" explicitly: if exactly one child is missing, recurse only into the other side. The recurrence is a four-case dispatch: empty tree, leaf, one missing child, both children present.

Recursive solution

def min_depth(root: Node | None) -> int:
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1                                   # this is the leaf
    if root.left  is None: return 1 + min_depth(root.right)
    if root.right is None: return 1 + min_depth(root.left)
    return 1 + min(min_depth(root.left), min_depth(root.right))

BFS: short-circuit on the first leaf

For minimum depth there's a much better algorithmic strategy than DFS: do a BFS, and return the depth of the first leaf you see. This visits exactly min_depth nodes, instead of touching the whole tree. Decisive win on long, thin trees (e.g., a chain of 10,000 single children).

from collections import deque

def min_depth_bfs(root) -> int:
    """BFS short-circuits on the first leaf — by far the fastest in practice
    when the tree is unbalanced (e.g., a sparse path of single children)."""
    if root is None: return 0
    q = deque([(root, 1)])
    while q:
        node, d = q.popleft()
        if node.left is None and node.right is None:
            return d
        if node.left:  q.append((node.left,  d + 1))
        if node.right: q.append((node.right, d + 1))

Trace

Tree:        2
              \
               3
                \
                 4
                  \
                   5
                    \
                     6

Wrong implementation: at every node, the absent left child says "depth 0",
so the algorithm walks down to a leaf with min == 0 trick — answer 1.

Correct recursive answer (no leaf except the bottom): walks down the only
chain, returns 5.

BFS: pops (2,1), pushes (3,2). pops (3,2), pushes (4,3). pops (4,3), pushes
(5,4). pops (5,4), pushes (6,5). pops (6,5), no children -> return 5.

The BFS version visits exactly d nodes, where d is the answer — orders of
magnitude faster than DFS on a degenerate tree.

Complexity

Recursive: O(n) time, O(h) stack.
BFS: O(n) worst case, but typically O(d) where d is the minimum depth itself. Best when the tree is unbalanced.

The trap to remember

Whenever you reuse a recurrence template by swapping max → min (or and → or), check what the identity element does to your base case. max has identity −∞ (so 0 is fine for missing children); min has identity +∞, so 0 is exactly wrong. This category of bug — wrong identity element for the aggregation — is the most common silent error in tree DPs.