Minimum Depth of Binary Tree

easy tree dfs bfs

Problem

Given a binary tree, find its minimum depth — the number of nodes along the shortest path from the root down to the nearest leaf. A leaf has no children.

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

Output2

9 is the nearest leaf at depth 2.

tree (level-order, "null" for empty)

from collections import deque
def min_depth(root):
    if not root: return 0
    q = deque([(root, 1)])
    while q:
        node, d = q.popleft()
        if not node.left and not node.right:
            return d
        if node.left: q.append((node.left, d + 1))
        if node.right: q.append((node.right, d + 1))

function minDepth(root) {
  if (!root) return 0;
  const q = [[root, 1]];
  while (q.length) {
    const [node, d] = q.shift();
    if (!node.left && !node.right) return d;
    if (node.left) q.push([node.left, d + 1]);
    if (node.right) q.push([node.right, d + 1]);
  }
}

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<Object[]> q = new ArrayDeque<>();
        q.offer(new Object[]{ root, 1 });
        while (!q.isEmpty()) {
            Object[] cur = q.poll();
            TreeNode n = (TreeNode) cur[0]; int d = (int) cur[1];
            if (n.left == null && n.right == null) return d;
            if (n.left != null) q.offer(new Object[]{ n.left, d + 1 });
            if (n.right != null) q.offer(new Object[]{ n.right, d + 1 });
        }
        return 0;
    }
}

int minDepth(TreeNode* root) {
    if (!root) return 0;
    queue<pair<TreeNode*, int>> q;
    q.push({ root, 1 });
    while (!q.empty()) {
        auto [n, d] = q.front(); q.pop();
        if (!n->left && !n->right) return d;
        if (n->left) q.push({ n->left, d + 1 });
        if (n->right) q.push({ n->right, d + 1 });
    }
    return 0;
}

Explanation

We want the shortest distance from the root to any leaf. The smartest way to find a shortest path is a breadth-first search (BFS): explore the tree level by level, and the very first leaf we bump into is guaranteed to be the nearest one.

We use a queue that holds pairs of (node, depth). We start with the root at depth 1. We repeatedly pull the front item, and if that node has no children it is a leaf — so we return its depth immediately.

If the node is not a leaf, we push its children onto the queue, each marked with depth + 1, and keep going. Because BFS visits shallower nodes before deeper ones, the first leaf popped is the shallowest leaf overall.

Example: for [3,9,20,null,null,15,7], we pop 3 (depth 1, has children), then pop 9 (depth 2). Node 9 has no children, so we stop and return 2.

This early exit is what makes BFS a great fit — we never explore the deeper 15 and 7 because we already found a closer leaf.

Time: O(n) Space: O(w) for the queue