Minimum Depth of Binary Tree

1. Define the problem

Given the root of a binary tree, return its minimum depth — the number of nodes along the shortest path from the root down to the nearest leaf node . A leaf has no children on either side. Use breadth-first search : the very first leaf a level-by-level queue dequeues is guaranteed to be the shallowest one, so you can return as soon as you find it , without exploring the rest of the tree.

Constraints

The number of nodes in the tree is in the range [0, 10⁵]
-1000 ≤ Node.val ≤ 1000

Example

Inputroot = [3, 9, 20, null, null, 15, 7]

Output2

Explanation The path 3 -> 9 reaches a leaf in 2 nodes, which is shorter than any path through 20.

2. Know the words first

In plain terms

Leaf node: A node with no left child and no right child — it sits at the end of a branch.

3. Visualize the solution

One cell per node, in level order — a value appears once the queue holds that node

d13

d2—

d3—

Statusdepth 1

Start at the root, 3, depth 1. It has two children, so it isn't a leaf — keep going.

What happens in this step

queue = [(3, depth 1)]

Dequeue 3. left=9, right=20 — both exist, so 3 is not a leaf.
Enqueue (9, depth 2) and (20, depth 2).

Step 1 of 4

Steps to visualize

The row has one slot for each of the tree's five nodes, top to bottom, left to right. A slot stays — until that node is enqueued, so slots that are never reached stay — forever.
Start a queue holding the root, tagged with depth 1.
Dequeue a node; if it has no children at all, its depth is the answer — stop immediately.
Otherwise enqueue its children, each tagged with depth + 1.
Because the queue processes shallower nodes first, the first leaf found is always the shallowest one.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per node, in level order — a value appears once the queue holds that node

d13

d2—

d3—

Statusdepth 1

Start at the root, 3, depth 1. It has two children, so it isn't a leaf — keep going.

What happens in this step

queue = [(3, depth 1)]

Dequeue 3. left=9, right=20 — both exist, so 3 is not a leaf.
Enqueue (9, depth 2) and (20, depth 2).

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function minDepth(values) {
  function buildTree(vals) {
    if (vals.length === 0 || vals[0] === null) return null;
    const root = { val: vals[0], left: null, right: null };
    const queue = [root];
    let i = 1;
    while (queue.length > 0 && i < vals.length) {
      const node = queue.shift();
      if (i < vals.length) {
        const leftVal = vals[i++];
        if (leftVal !== null) {
          node.left = { val: leftVal, left: null, right: null };
          queue.push(node.left);
        }
      }
      if (i < vals.length) {
        const rightVal = vals[i++];
        if (rightVal !== null) {
          node.right = { val: rightVal, left: null, right: null };
          queue.push(node.right);
        }
      }
    }
    return root;
  }

  const root = buildTree(values);
  if (!root) return 0;

  const queue = [[root, 1]];

  while (queue.length > 0) {
    const [node, depth] = queue.shift();
    if (!node.left && !node.right) return depth;
    if (node.left) queue.push([node.left, depth + 1]);
    if (node.right) queue.push([node.right, depth + 1]);
  }

  return 0;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`root = [3, 9, 20, null, null, 15, 7]`	`2`	example from the docstring
`root = [1]`	`1`	smallest valid input, a single node
`root = []`	`0`	empty tree edge case
`root = [2, null, 3, null, 4, null, 5]`	`4`	a chain of single-child nodes — depth stops only at a true leaf
`root = [1, 2, 3, 4, 5, 6, 7]`	`3`	balanced full tree where every leaf sits at the same depth
`root = [1, 2, 3]`	`2`	first level already contains a leaf
`root = [1, 2, null, 3]`	`3`	left-skewed chain with no shortcut

Minimum Depth of Binary Tree