172. Minimum Tree Depth with BFS

Why this mechanism works

BFS processes candidate endpoints by increasing depth. Consequently the first actual leaf removed from the queue is the nearest leaf, and search can stop. Carry depth alongside each node so the return value is already known at discovery of the endpoint.

State and boundaries

Queue entries (node,depth) have nondecreasing depth, and depth counts nodes from the root through that node.

Protocol

1. Return zero for None.
2. Enqueue (root,1).
3. Remove the next entry.
4. Return its depth if both children are absent.
5. Enqueue each real child with depth+1.

Visualization

1 -> left 2 -> left 3
depths 1,2,3; only node 3 is a leaf
missing right children do not terminate a path

Python implementation

from collections import deque
from structures import build_tree

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 min_depth: if root is None:
root=N1(val=1,left=N2,right=N3)

L7 min_depth: queue = deque([(root, 1)])
root=N1(val=1,left=N2,right=N3); queue=deque([(N1(val=1,left=N2,right=N3), 1)])

L9 min_depth: node, depth = queue.popleft()
root=N1(val=1,left=N2,right=N3); queue=deque([]); node=N1(val=1,left=N2,right=N3); depth=1

L12 min_depth: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=N3); queue=deque([]); node=N1(val=1,left=N2,right=N3); depth=1; child=N2(val=2,left=N4,right=None)

L14 min_depth: queue.append((child, depth + 1))
root=N1(val=1,left=N2,right=N3); queue=deque([(N2(val=2,left=N4,right=None), 2)]); node=N1(val=1,left=N2,right=N3); depth=1; child=N2(val=2,left=N4,right=None)

L12 min_depth: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=N3); queue=deque([(N2(val=2,left=N4,right=None), 2)]); node=N1(val=1,left=N2,right=N3); depth=1; child=N3(val=3,left=None,right=None)

L14 min_depth: queue.append((child, depth + 1))
root=N1(val=1,left=N2,right=N3); queue=deque([(N2(val=2,left=N4,right=None), 2), (N3(val=3,left=None,right=None), 2)]); node=N1(val=1,left=N2,right=N3); depth=1; child=N3(val=3,left=None,right=None)

L9 min_depth: node, depth = queue.popleft()
root=N1(val=1,left=N2,right=N3); queue=deque([(N3(val=3,left=None,right=None), 2)]); node=N2(val=2,left=N4,right=None); depth=2; child=N3(val=3,left=None,right=None)

L12 min_depth: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=N3); queue=deque([(N3(val=3,left=None,right=None), 2)]); node=N2(val=2,left=N4,right=None); depth=2; child=N4(val=4,left=None,right=None)

L14 min_depth: queue.append((child, depth + 1))
root=N1(val=1,left=N2,right=N3); queue=deque([(N3(val=3,left=None,right=None), 2), (N4(val=4,left=None,right=None), 3)]); node=N2(val=2,left=N4,right=None); depth=2; child=N4(val=4,left=None,right=None)

L12 min_depth: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=N3); queue=deque([(N3(val=3,left=None,right=None), 2), (N4(val=4,left=None,right=None), 3)]); node=N2(val=2,left=N4,right=None); depth=2; child=None

L9 min_depth: node, depth = queue.popleft()
root=N1(val=1,left=N2,right=N3); queue=deque([(N4(val=4,left=None,right=None), 3)]); node=N3(val=3,left=None,right=None); depth=2; child=None

L5 min_depth: if root is None:
root=N1(val=1,left=N2,right=None)

L7 min_depth: queue = deque([(root, 1)])
root=N1(val=1,left=N2,right=None); queue=deque([(N1(val=1,left=N2,right=None), 1)])

L9 min_depth: node, depth = queue.popleft()
root=N1(val=1,left=N2,right=None); queue=deque([]); node=N1(val=1,left=N2,right=None); depth=1

L12 min_depth: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=None); queue=deque([]); node=N1(val=1,left=N2,right=None); depth=1; child=N2(val=2,left=N3,right=None)

L14 min_depth: queue.append((child, depth + 1))
root=N1(val=1,left=N2,right=None); queue=deque([(N2(val=2,left=N3,right=None), 2)]); node=N1(val=1,left=N2,right=None); depth=1; child=N2(val=2,left=N3,right=None)

L12 min_depth: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=None); queue=deque([(N2(val=2,left=N3,right=None), 2)]); node=N1(val=1,left=N2,right=None); depth=1; child=None

L9 min_depth: node, depth = queue.popleft()
root=N1(val=1,left=N2,right=None); queue=deque([]); node=N2(val=2,left=N3,right=None); depth=2; child=None

L12 min_depth: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=None); queue=deque([]); node=N2(val=2,left=N3,right=None); depth=2; child=N3(val=3,left=None,right=None)

L14 min_depth: queue.append((child, depth + 1))
root=N1(val=1,left=N2,right=None); queue=deque([(N3(val=3,left=None,right=None), 3)]); node=N2(val=2,left=N3,right=None); depth=2; child=N3(val=3,left=None,right=None)

L12 min_depth: for child in (node.left, node.right):
root=N1(val=1,left=N2,right=None); queue=deque([(N3(val=3,left=None,right=None), 3)]); node=N2(val=2,left=N3,right=None); depth=2; child=None

L9 min_depth: node, depth = queue.popleft()
root=N1(val=1,left=N2,right=None); queue=deque([]); node=N3(val=3,left=None,right=None); depth=3; child=None

Why the solution is correct

FIFO insertion ensures every depth-d node is processed before any depth-(d+1) node. Thus no unprocessed leaf can have smaller depth than the first leaf returned. Enqueued depths are exact because each child adds one node to its parent's path.

Time and space

O(n) worst-case time and O(w) queue space; often stops before visiting the whole tree.

Common mistakes

Using 1+min(left_depth,right_depth) without handling missing children incorrectly shortens single-child chains. A node with only one missing child is not a leaf.

Reasoning card

Transfer exercise

Implement recursive minimum depth with explicit cases for zero, one, and two children.