Minimum Depth of Binary Tree

EasyTree BFSGrokkingJuniorOpen on LeetCodeUpdated Nov 11, 2026

You're given the root of a binary tree. Return its minimum depth: the number of nodes on the shortest path from the root down to a leaf, where a leaf is a node with no children. A node with one child is not a leaf, so a path through it must continue into that child. An empty tree has minimum depth 0.

Examples

root = [3,9,20,null,null,15,7] returns 2

The leaf 9 sits at depth 2.

9 has no children, so the path 3 -> 9 reaches a leaf after 2 nodes. The leaves 15 and 7 are one level deeper.

root = [2,null,3,null,4,null,5,null,6] returns 5

A single chain: the first leaf is the last node.

Every node has only a right child, so the only leaf is 6, and reaching it takes all 5 nodes.

root = [] returns 0

An empty tree has no path at all, so its minimum depth is 0.

Constraints

0 <= number of nodes <= 10^5
-1000 <= Node.val <= 1000

Hints

Hint 1

You want the leaf closest to the root. Which traversal reaches nodes in order of their distance from the root?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Breadth-first search (BFS) visits nodes in order of depth, so the first leaf it reaches is a shallowest one. Process the queue one level at a time with a depth counter, and return the depth as soon as you pop a node with no children. BFS can stop at the shallowest leaf without exploring deeper branches, which a depth-first search would still visit. In the worst case, such as a single chain or a full tree, every node is visited.

Time

O(n)

Space

O(n)

Pitfall

Adapting Maximum Depth as 1 + min(minDepth(left), minDepth(right)) treats a missing child as a path of depth 0, so the chain [2,null,3,null,4,null,5,null,6] returns 1 instead of 5. A missing child doesn't lead to a leaf, so it can't count as the shorter side.

Solutions

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int depth = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            depth++;
        }
        return depth;
    }
}

from collections import deque
from typing import Optional

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue = deque([root])
        depth = 1
        while queue:
            for _ in range(len(queue)):
                node = queue.popleft()
                if not node.left and not node.right:
                    return depth
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        return depth