LeetCode 111: Minimum Depth of Binary Tree

Problem Restatement

We are given the root of a binary tree.

We need to return its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf is a node with no children.

For this tree:

The nearest leaf is 9.

The path is:

3 -> 9

This path contains 2 nodes, so the answer is:

Input and Output

Item	Meaning
Input	`root`, the root node of a binary tree
Output	Minimum number of nodes from root to nearest leaf
Empty tree	Return `0`
Leaf	A node with no left child and no right child
Important detail	A node with one child is not a leaf

LeetCode gives the TreeNode class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The function shape is:

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        ...

Examples

Consider:

The root-to-leaf paths are:

3 -> 9
3 -> 20 -> 15
3 -> 20 -> 7

Their depths are:

2
3
3

The minimum depth is:

Now consider a skewed tree:

There is only one root-to-leaf path:

2 -> 3 -> 4 -> 5 -> 6

So the answer is:

For an empty tree:

root = None

The answer is:

First Thought: Use Breadth-First Search

The problem asks for the shortest path from the root to a leaf.

In a tree, breadth-first search visits nodes by depth:

depth 1
depth 2
depth 3
...

So the first leaf found by BFS is the nearest leaf.

That means we can stop early. We do not need to visit the whole tree if a shallow leaf appears first.

Key Insight

Use a queue that stores pairs:

(node, depth)

Start with:

(root, 1)

Then process nodes from the queue.

When we remove a node from the queue:

If it is a leaf, return its depth.
Otherwise, add its children with depth depth + 1.

Because BFS processes smaller depths before larger depths, the first leaf gives the minimum depth.

Algorithm

If root is None, return 0.

Otherwise:

Create a queue containing (root, 1).
While the queue has nodes:
1. Remove the front pair (node, depth).
2. If node has no left child and no right child, return depth.
3. If node.left exists, add (node.left, depth + 1).
4. If node.right exists, add (node.right, depth + 1).

Correctness

Breadth-first search processes nodes in increasing depth order.

The queue starts with the root at depth 1. When a node at depth d is processed, its children are added with depth d + 1. Since the queue is first-in-first-out, all nodes at depth d are processed before any node at depth d + 1.

A valid minimum-depth path must end at a leaf. The algorithm returns only when it reaches a node with no children.

The first leaf reached by BFS has the smallest possible depth among all leaves, because no deeper node can be processed before all shallower nodes. Therefore, returning that depth gives the minimum depth of the tree.

Complexity

Metric	Value	Why
Time	`O(n)`	In the worst case, BFS may visit every node
Space	`O(n)`	The queue may hold many nodes from one level

Here, n is the number of nodes in the tree.

BFS may stop early if it finds a shallow leaf.

Implementation

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        q = deque([(root, 1)])

        while q:
            node, depth = q.popleft()

            if node.left is None and node.right is None:
                return depth

            if node.left is not None:
                q.append((node.left, depth + 1))

            if node.right is not None:
                q.append((node.right, depth + 1))

        return 0

Code Explanation

Handle the empty tree:

if root is None:
    return 0

Initialize the queue:

q = deque([(root, 1)])

The root has depth 1 because depth counts nodes, not edges.

Process nodes in BFS order:

while q:
    node, depth = q.popleft()

Check whether the current node is a leaf:

if node.left is None and node.right is None:
    return depth

If this is the first leaf reached, BFS guarantees it has minimum depth.

Add existing children:

if node.left is not None:
    q.append((node.left, depth + 1))

if node.right is not None:
    q.append((node.right, depth + 1))

The final return 0 is only a safety fallback.

Testing

from collections import deque
from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        q = deque([(root, 1)])

        while q:
            node, depth = q.popleft()

            if node.left is None and node.right is None:
                return depth

            if node.left is not None:
                q.append((node.left, depth + 1))

            if node.right is not None:
                q.append((node.right, depth + 1))

        return 0

def run_tests():
    s = Solution()

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(20, TreeNode(15), TreeNode(7)),
    )
    assert s.minDepth(root1) == 2

    root2 = TreeNode(
        2,
        None,
        TreeNode(3, None, TreeNode(4, None, TreeNode(5, None, TreeNode(6)))),
    )
    assert s.minDepth(root2) == 5

    root3 = None
    assert s.minDepth(root3) == 0

    root4 = TreeNode(1)
    assert s.minDepth(root4) == 1

    root5 = TreeNode(
        1,
        TreeNode(2, TreeNode(4), None),
        TreeNode(3),
    )
    assert s.minDepth(root5) == 2

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`[3,9,20,null,null,15,7]`	Standard example where nearest leaf is shallow
`[2,null,3,null,4,null,5,null,6]`	Skewed tree, only one leaf
Empty tree	Confirms base case
Single node	Root itself is a leaf
Mixed tree	Confirms BFS stops at nearest leaf