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.

Example 1:

Input: root = [5,3,8,null,null,6,9]
Output: 2
Explanation: the shortest root-to-leaf path is 5 -> 3; the 8-side paths reach depth 3.
 
    5
   / \
  3   8
     / \
    6   9

Example 2:

Input: root = [2,null,5,null,8]
Output: 3
Explanation: the only path is 2 -> 5 -> 8.
 
  2
   \
    5
     \
      8

Constraints:

• 0 <= TreeNode.val <= 10^3
• The number of nodes in the tree is in the range [0, 10^3].

Solution Breakdown

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. The first leaf BFS dequeues is therefore 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 -> 5 -> 8: we pop (2, 1), node 2 has a right child so it is not a leaf, enqueue (5, 2); pop (5, 2), also one child, enqueue (8, 3); pop (8, 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.