Minimum Depth of Binary Tree (LC 111)

Pattern: BFS — Shortest Path to a Leaf (or careful DFS)
Difficulty: Easy
Key Concept: Minimum depth = shortest path from root to a leaf (node with no children). BFS finds the nearest leaf first; naive DFS can explore deep branches before a shallow leaf on another branch

Problem Statement

Given the root of a binary tree, return its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root down to the nearest leaf node.

Input: TreeNode root.
Output: int — depth measured as node count on that path (root counts as depth 1).

Important: A leaf has both left == null and right == null. A node with only one child is not a leaf; the path must continue through that child.

1. Algorithm & Pseudocode

Optimal — BFS

function minDepth(root):
    if root is null:
        return 0

    queue = queue of (node, depth) or use level counter
    enqueue (root, 1)

    while queue not empty:
        (node, d) = dequeue

        if node.left is null AND node.right is null:
            return d    // first leaf found = closest leaf (BFS order)

        if node.left != null:
            enqueue (node.left, d + 1)
        if node.right != null:
            enqueue (node.right, d + 1)

Brute force — DFS (explores whole tree)

function dfs(node):
    if node is null:
        return infinity (or handle caller)
    if node is leaf:
        return 1
    if only left child:
        return 1 + dfs(node.left)
    if only right child:
        return 1 + dfs(node.right)
    return 1 + min(dfs(left), dfs(right))

Naive return 1 + min(dfs(left), dfs(right)) without handling one-missing-child cases wrongly treats a missing child as depth 0 and undercounts (classic bug).

2. Step-by-Step Analysis (Beginner-Friendly)

Why BFS for “minimum”? BFS expands nodes in order of increasing distance from the root. The first time you dequeue a leaf, you have found the shortest root-to-leaf path in terms of edge count (or node count, depending on convention — here LeetCode uses nodes, so we start depth at 1 at root).
Why is DFS “brute force” in spirit? A correct DFS still visits the whole tree in the worst case (e.g., you might need the whole tree to know the minimum). Early stopping is harder than in BFS. Interviewers still accept DFS if you handle one-child nodes correctly.
The one-child trap: For a node with only a right child, the leaf might be deep under that right chain. If you treat null as depth 0 and do min(left, right) + 1, you incorrectly think the path “ends” at the current node. You must not count a non-leaf as the answer.
Empty tree: root == null → depth 0 (LeetCode convention).
Why not “minimum height” via only right pointers? That is a different problem; here you must follow the actual tree structure.

3. The Dry Run

Tree A — `[3,9,20,null,null,15,7]`

Leaves: 9, 15, 7. Shortest root-to-leaf path: 3 → 9 (length 2 nodes).

BFS (queue stores node; depth shown as level when dequeued). We use “depth = number of nodes from root to current node.”

Dequeue order	Node	Depth `d`	Leaf? (`L==null && R==null`)	Action
1	3	1	No	enqueue 9, 20
2	9	2	Yes	return 2

Answer for Tree A: 2.

Tree B — skewed `[2,null,3,null,4,null,5,null,6]`

Only leaf is 6. Path 2→3→4→5→6 has 5 nodes.

BFS trace

Step	Dequeue	Depth `d`	Leaf?	Queue after (left→right)
Init	—	—	—	`[2]`
1	2	1	No (only right child)	`[3]`
2	3	2	No	`[4]`
3	4	3	No	`[5]`
4	5	4	No	`[6]`
5	6	5	Yes	`[]` → return 5

Answer for Tree B: 5.

Why BFS shines: If there were a shallow leaf on an early level, you would return immediately and never walk the whole chain. DFS on a skewed tree still runs O(n) but does not stop early the same way; BFS’s first leaf rule matches “minimum depth” directly.

4. Java Solution

Brute Force

DFS that visits subtrees; must handle one-child cases. Worst case still O(n) time, O(h) stack. “Brute force” here means less intuitive and easy to get wrong, not necessarily larger big-O.

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return dfs(root);
    }

    private int dfs(TreeNode node) {
        if (node.left == null && node.right == null) {
            return 1;
        }
        if (node.left == null) {
            return 1 + dfs(node.right);
        }
        if (node.right == null) {
            return 1 + dfs(node.left);
        }
        return 1 + Math.min(dfs(node.left), dfs(node.right));
    }
}

Optimal

BFS — return as soon as a leaf is popped. Time: O(n) worst case (may need full tree), Space: O(w) for queue.

import java.util.*;

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                if (node.left == null && node.right == null) {
                    return depth;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            depth++;
        }

        return depth;
    }
}

5. The “Java vs. Others” Edge

Leaf check in Java: node.left == null && node.right == null is explicit and readable.
BFS queue: LinkedList as Queue is standard; ArrayDeque is also fine for offer/poll.
DFS bug: return 1 + Math.min(minDepth(left), minDepth(right)) without special-casing one null child is wrong — you would take min(0, deep) and report a too-small depth. The brute-force DFS above fixes that by only taking min when both children exist.
Compared to “shortest path” in graphs: Same idea — BFS finds shortest path in an unweighted setting; here the “graph” is the tree.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force (DFS)	O(n)	O(h)	h = height; must handle single-child nodes; visits whole tree worst case
Optimal (BFS)	O(n)	O(w)	Stops at first leaf; best for wide shallow trees; queue up to width w

n = number of nodes. For BFS, worst-case space is O(n) at the widest level; for DFS, O(n) skewed stack.