Minimum Depth of Binary Tree (LeetCode 111)

The problem

You get the root of a binary tree. Return its minimum depth: the number of nodes on the shortest path from the root down to a leaf (a node with no children). An empty tree has depth 0.

Input:      3
           / \
          9   20
             /  \
            15   7

Output: 2

The leaf 9 is reached by 3 -> 9, which is 2 nodes. The leaves 15 and 7 are deeper.

How to think about it

Start with brute force. Recurse: the minimum depth is 1 + min(left depth, right depth). That visits every node even when a leaf sits right below the root, and it hides a trap. If a node has only one child, the missing side has depth 0, so min picks 0 and you count a path that doesn’t end at a leaf.

The key insight: BFS meets nodes in order of depth. A queue explores every node at depth 1, then every node at depth 2, and so on. So the first leaf you pop is the shallowest leaf, and you can return its depth immediately. You never touch the deeper parts of the tree. On a lopsided tree with one short branch, that’s a huge saving.

Carry the depth in the queue. Store (node, depth) pairs. When you push a child, push depth + 1 with it.

Which pattern is this? Tree BFS. The tell is ”minimum / shortest / nearest” on a tree or unweighted graph: BFS finds it first, DFS has to search everything.

Approach

1. If root is None, return 0.
2. Start the queue with (root, 1).
3. Pop (node, d):
   • if node has no children, return d,
   • otherwise push each existing child with d + 1.

Solution

from collections import deque

def min_depth(root):
    if not root: return 0
    q = deque([(root, 1)])                        # (node, depth)
    while q:
        node, d = q.popleft()
        if not node.left and not node.right: return d   # first leaf = shallowest leaf
        if node.left: q.append((node.left, d + 1))
        if node.right: q.append((node.right, d + 1))
# min_depth([3,9,20,null,null,15,7]) -> 2

Dry run

On the example tree:

Two pops and it’s done; 20, 15 and 7 are never expanded.

Complexity

• Time: O(n) in the worst case (for example, a perfect tree, where all leaves are at the bottom). Often far less, because BFS stops at the first leaf.
• Space: O(w), the widest level held in the queue; O(n) in the worst case.

Edge cases and pitfalls

• Empty tree: returns 0.
• Single node: it is a leaf, so the answer is 1.
• A node with one child is not a leaf. For [1, 2] (root with only a left child), the answer is 2, not 1. The naive 1 + min(left, right) recursion gets this wrong.
• Counting edges instead of nodes. This problem counts nodes; start at depth 1.
• Confusing it with maximum depth. Max depth has no early exit; BFS or DFS must see every node.

Related problems

• Maximum Depth of Binary Tree (LeetCode 104): the opposite question, usually solved with DFS.
• Rotting Oranges (LeetCode 994): BFS distance on a grid, from many starting points.
• Word Ladder (LeetCode 127): the same “BFS, return at the first hit” idea on an implicit graph.