What is the brute force approach and complexity for Minimum Depth of Binary Tree?

Recurse to every leaf and keep the smallest depth seen with time complexity O(N) and space complexity O(H).

What is the optimal approach and complexity for Minimum Depth of Binary Tree?

Level-order queue; return the round number when the first leaf is popped with optimal time complexity O(N) and space complexity O(W).

How do you identify the pattern for Minimum Depth of Binary Tree?

Look for key signals in the prompt: "minimum depth" indicates We want a number of levels (nodes on a path), not a sum and not the path itself.; "closest leaf" indicates The nearest end of a route. In a tree, BFS reaches nodes in order of distance, so the first match is the shortest.; "a leaf has no children" indicates A node with one child is not a stop. The leaf test has to check both children..

Minimum Depth of Binary Tree

Easy·LeetCode #111Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree BFS: shortest distance (minimum depth)

Complexity:O(N)→O(N)

Key Insight

Go through the tree one level at a time with a queue. The first leaf we pop is the closest one, because levels come out from shallow to deep. Return the round number at that moment. Nothing deeper can beat it.

Core Validity Invariant

The first leaf popped from the queue is at the smallest depth of any leaf, so its round number is the minimum depth.

Problem

You are given the root of a binary tree. Return its minimum depth.

The depth of a node is the number of nodes on the path from the root down to it, so the root has depth 1. A leaf is a node with no children. The minimum depth is the depth of the closest leaf.

A node with only one child is not a leaf, so the walk cannot stop there.

Input

The root of a binary tree. The tree can be empty.

Output

One number: the minimum depth. An empty tree has depth 0.

Example 1

Input: root = [3, 9, 20, null, null, 15, 7]

Output: 2

Node 9 is a leaf at depth 2 (the path is 3 → 9). That is the closest leaf.

Example 2

Input: root = [2, null, 3, null, 4, null, 5, null, 6]

Output: 5

The tree is one chain: 2 → 3 → 4 → 5 → 6. The only leaf is 6, at depth 5. Node 2 has only one child, so it is not a leaf.

Constraints

• 0 ≤ number of nodes ≤ 10^5
• −1000 ≤ Node.val ≤ 1000

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Max Depth asks for the deepest node. This asks for the closest leaf. What changes in the code?
2.
Is a node with only one child a leaf? What should the walk do at that node?
3.
If I go level by level, which leaf do I meet first? Is that the closest one?
4.
Do I count depth once per node or once per round? What goes wrong if I count per node?
5.
When I find a leaf, can a later leaf still be shallower? How would I know?

Brute force approach

Idea

Walk every path from the root down to a leaf with DFS. Pass the depth down as you go. When a leaf is reached, record its depth and keep the smallest one. DFS cannot tell which leaf is closest, so it has to check them all.

Thinking process

1
The answer is the depth of some leaf, so only leaves matter.
2
Recursion walks one path at a time. Pass the depth down: each child is one level deeper. When the walk reaches a leaf, that depth is one candidate.
3
On [3, 9, 20, null, null, 15, 7]: the path 3 → 9 gives depth 2. The path 3 → 20 → 15 gives 3, and 3 → 20 → 7 gives 3. The smallest is 2.
4
DFS never stops early. On [1, 2, 3, 4, null, null, 5, 6, 7] it goes 1 → 2 → 4 → 6, then 7, then back up to 3 → 5. It visits all 7 nodes, even though leaf 5 (depth 3) is the closest and it is found last.

Visual

Circles are tree nodes. Green = already visited, blue = visiting now, purple = the best leaf so far. The number under a node is its depth. DFS does not stop at the first leaf it finds.

DFS visits every pathroot = [1, 2, 3, 4, null, null, 5, 6, 7]step 1/8

Current root path (top → bottom)

State

depth here: 1
best so far: —
nodes visited: 1

1 is not a leaf → keep going down

Visit 1 at depth 1, which is not a leaf, so DFS keeps going down.

Code & Implementation

brute.cpp

// struct TreeNode { int val; TreeNode *left; TreeNode *right; };  (given by LeetCode)
class Solution {
    // Walks every path down from `node`. `depth` = nodes above this node on the path.
    void walk(TreeNode* node, int depth, int& best) {
        if (!node) return;
        depth++;                           // count this node
        if (!node->left && !node->right) {
            best = min(best, depth);       // a leaf ends the path: record its depth
            return;
        }
        // Not a leaf: keep going. We never stop early, even after a shallow leaf.
        walk(node->left, depth, best);
        walk(node->right, depth, best);
    }

public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        int best = INT_MAX;
        walk(root, 0, best);
        return best;
    }
};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Walks every path down from `node`. `depth` = nodes above this node on the path.
    private void walk(TreeNode node, int depth, int[] best) {
        if (node == null) return;
        depth++;                           // count this node
        if (node.left == null && node.right == null) {
            best[0] = Math.min(best[0], depth); // a leaf ends the path: record its depth
            return;
        }
        // Not a leaf: keep going. We never stop early, even after a shallow leaf.
        walk(node.left, depth, best);
        walk(node.right, depth, best);
    }

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int[] best = {Integer.MAX_VALUE};
        walk(root, 0, best);
        return best[0];
    }
}

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 not root:
            return 0

        best = [float("inf")]

        # Walks every path down from `node`. `depth` = nodes above this node on the path.
        def walk(node: Optional[TreeNode], depth: int) -> None:
            if not node:
                return
            depth += 1                           # count this node
            if not node.left and not node.right:
                best[0] = min(best[0], depth)    # a leaf ends the path: record its depth
                return
            # Not a leaf: keep going. We never stop early, even after a shallow leaf.
            walk(node.left, depth)
            walk(node.right, depth)

        walk(root, 0)
        return int(best[0])

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

// Walks every path down from `node`. `depth` = nodes above this node on the path.
function walk(node: TreeNode | null, depth: number, best: { val: number }): void {
    if (!node) return;
    depth++;                           // count this node
    if (!node.left && !node.right) {
        best.val = Math.min(best.val, depth); // a leaf ends the path: record its depth
        return;
    }
    // Not a leaf: keep going. We never stop early, even after a shallow leaf.
    walk(node.left, depth, best);
    walk(node.right, depth, best);
}

export function minDepth(root: TreeNode | null): number {
    if (!root) return 0;
    const best = { val: Infinity };
    walk(root, 0, best);
    return best.val;
}

Complexity

Time O(N)Space O(H)

Every node is visited once, so the time is O(N). The optimal has the same worst-case time. What BFS improves is how much it visits: it stops at the first leaf it pops, so a shallow leaf saves the rest of the tree. The trade-off is space. This DFS keeps one root path, so it uses O(H), the tree height. BFS keeps a whole level in its queue, so it uses O(W), the widest level.

Optimized approach

Idea

Start from brute force

DFS checked every leaf and then took the smallest depth. Level order meets the leaves in order of depth, so the first leaf it meets is already the smallest.

Find the repeated work

The DFS keeps walking deep paths after it already has a short leaf. Those paths can never give a smaller answer, but the DFS still visits them. Level order stops at the answer's level, so it never does that work.

Define the state — what variables do I need?

queue: Nodes waiting to be popped, in order of depth. A popped node's children go to the back.
depth: The round number, which is the depth of the nodes popped in this round (the root's depth is 1).
size: How many nodes were in the queue when the round started. Those are exactly the nodes of this level.

Define validity

The first leaf popped from the queue is at the smallest depth of any leaf, so its round number is the minimum depth.

Define the transitions — when does each pointer move, and why is it safe?

Start

queue = [root]; depth = 0

The root is the only node on the first level. Depth becomes 1 when the first round starts.

Start of each round

depth++; size = queue.size()

The queue holds only this level's nodes at this point. Children pushed during the round belong to the next level, so the loop pops exactly size nodes.

Pop a node with no children

return depth

Every node popped earlier was at this depth or shallower, and none of them was a leaf. So this is the shallowest leaf.

Pop a node with children

push its left and right child (if they exist)

A child is one level deeper, so it goes to the back of the queue and waits for the next round.

What does the current window add to the answer?

The loop adds 1 to depth each round. When the first leaf pops, depth is the number of nodes on its path from the root, which is the answer.

Code & Implementation

optimal.cpp

// struct TreeNode { int val; TreeNode *left; TreeNode *right; };  (given by LeetCode)
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;

        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;

        while (!q.empty()) {
            // One round = one level. Count the round, not each node.
            depth++;
            int size = q.size();           // nodes on this level; children pushed now belong to the next one
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                // Levels come out in order, so the first leaf we pop is the closest one.
                if (!node->left && !node->right) return depth;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return 0;   // not reached: a non-empty tree always has a leaf
    }
};

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int depth = 0;

        while (!q.isEmpty()) {
            // One round = one level. Count the round, not each node.
            depth++;
            int size = q.size();           // nodes on this level; children pushed now belong to the next one
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                // Levels come out in order, so the first leaf we pop is the closest one.
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
        }
        return 0;   // not reached: a non-empty tree always has a leaf
    }
}

from typing import Optional
from collections import deque

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 not root:
            return 0

        q: deque[TreeNode] = deque([root])
        depth = 0

        while q:
            # One round = one level. Count the round, not each node.
            depth += 1
            size = len(q)           # nodes on this level; children pushed now belong to the next one
            for _ in range(size):
                node = q.popleft()
                # Levels come out in order, so the first leaf we pop is the closest one.
                if not node.left and not node.right:
                    return depth
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return 0   # not reached: a non-empty tree always has a leaf

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function minDepth(root: TreeNode | null): number {
    if (!root) return 0;

    const q: TreeNode[] = [root];
    let depth = 0;

    while (q.length > 0) {
        // One round = one level. Count the round, not each node.
        depth++;
        const size = q.length;           // nodes on this level; children pushed now belong to the next one
        for (let i = 0; i < size; i++) {
            const node = q.shift()!;
            // Levels come out in order, so the first leaf we pop is the closest one.
            if (!node.left && !node.right) return depth;
            if (node.left) q.push(node.left);
            if (node.right) q.push(node.right);
        }
    }
    return 0;   // not reached: a non-empty tree always has a leaf
}

Complexity

Time O(N)Space O(W)

The worst case is still O(N): if the closest leaf is at the bottom, every node is popped. The best case is much faster, because the search stops at the first leaf. The queue holds about one level's worth of nodes at a time, so space is O(W), the widest level, instead of the O(H) of the DFS.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recurse to every leaf and keep the smallest depth seen	O(N)	O(H)
Optimal	Level-order queue; return the round number when the first leaf is popped	O(N)	O(W)

Why does this belong to this pattern?

Clues in the problem statement

“minimum depth”We want a number of levels (nodes on a path), not a sum and not the path itself.
“closest leaf”The nearest end of a route. In a tree, BFS reaches nodes in order of distance, so the first match is the shortest.
“a leaf has no children”A node with one child is not a stop. The leaf test has to check both children.

Tree, answer is a depth+shortest route to any leaf+level by level (BFS)+stop at the first leaf→Tree BFS: shortest distance (minimum depth)

Maximum Depth (LC 104) asks for the deepest node, so a DFS with 1 + max(left, right) is the natural fit. This question asks for the closest leaf. BFS reaches nodes in order of depth, so the first leaf it pops is the shortest route. The one extra rule is the leaf test: a leaf has no children at all, so a node with one child is not a stop.

Don't make this mistake

Copying Maximum Depth: `1 + min(left, right)`

✗ int minDepth(TreeNode* root) { if (!root) return 0; return 1 + min(minDepth(root->left), minDepth(root->right)); }

✓ int minDepth(TreeNode* root) { if (!root) return 0; if (!root->left) return 1 + minDepth(root->right); if (!root->right) return 1 + minDepth(root->left); return 1 + min(minDepth(root->left), minDepth(root->right)); }

This is the pattern-confusion trap. Maximum Depth uses max, and the copy changes it to min. But a missing child returns 0, and min picks that 0. On [2, null, 3, null, 4, null, 5, null, 6], node 2 has no left child, so min(0, …) is 0 and the code returns 1. The correct answer is 5: node 2 has one child, so it is not a leaf, and the walk must go down to 6.

A node with one child counts as a leaf

✗ if (!node->left || !node->right) return depth; // BFS leaf test

✓ if (!node->left && !node->right) return depth;

|| makes a node with one child end the search. On [1, 2, 3, 4, null, null, 5, 6, 7], node 2 has only a left child (4). It is popped first in round 2, so the code returns 2. The correct answer is 3, from leaf 5.

Counting depth per node instead of per round

✗ while (!q.empty()) { int size = q.size(); for (int i = 0; i < size; i++) { depth++; // runs once per node ...

✓ while (!q.empty()) { depth++; // once per round, before the for loop int size = q.size(); for (int i = 0; i < size; i++) {

depth has to be the level number. Increasing it per node makes a level with two nodes add 2. On [1, 2, 3, 4, null, null, 5, 6, 7], leaf 5 is the 5th node popped, so the code returns 5 instead of 3.

Returning the first leaf that DFS meets

✗ int dfs(TreeNode* node, int depth) { // call with depth = 1 for the root if (!node) return 0; if (!node->left && !node->right) return depth; int left = dfs(node->left, depth + 1); if (left) return left; return dfs(node->right, depth + 1); }

A left-first DFS takes the first leaf it reaches, not the closest one. On [1, 2, 3, 4, null, null, 5, 6, 7] it goes 1 → 2 → 4 → 6 and returns 4. Leaf 5 at depth 3 is the answer. Only a level-by-level walk meets shallow leaves first.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree BFS translate into production architectures and low-level memory mechanics.

LLD Architecture