Minimum Depth of Binary Tree

Problem

Monitoring systems model call graphs as trees and alert on paths that exceed depth thresholds. Finding the minimum depth - the shortest root-to-leaf path - lets you quickly check whether any execution path is shorter than expected. BFS is the natural fit: it stops the instant it reaches the first leaf, guaranteed to be the shallowest.

    3
   / \
  9  20
    /  \
   15   7
→ minimum depth = 2 (path: 3 → 20 → 7 or 3 → 20 → 15)
 
    2
     \
      3
       \
        4
→ minimum depth = 3 (only path: 2 → 3 → 4)

Solution

Approach: level-order BFS with stop-on-first-leaf.

The minimum depth is the shortest root-to-leaf path, and BFS reaches nodes in strictly increasing order of depth. That ordering is the whole trick: the first leaf BFS dequeues is guaranteed to sit at the shallowest leaf level, because every node closer to the root was already dequeued and none of them was a leaf. So we can return the moment we pop a leaf instead of exploring the whole tree. We seed the queue with (root, 1) - depth 1 because the path length counts nodes, not edges - and on each pop test whether the node is a leaf (node.left is None and node.right is None). If it is, we return its depth immediately; otherwise we enqueue each existing child with depth + 1.

Trace the right-skewed tree 2 -> 3 -> 4: we pop (2, 1), node 2 has a right child so it is not a leaf, enqueue (3, 2); pop (3, 2), also one child, enqueue (4, 3); pop (4, 3), both children None, return 3. A node with a single child is deliberately not treated as a leaf - returning at it would report a depth shorter than any real root-to-leaf path.

Edge cases: an empty tree (root is None) returns 0 before the loop. A one-child node is correctly skipped, so a tree that is a single chain returns its full length rather than stopping early.

Complexity: O(n) time worst case (a tree with all leaves at the bottom forces a full visit), O(w) space where w is the maximum tree width - the queue holds at most one level at a time.