Minimum depth of a binary tree

"Find the minimum depth of a binary tree." It sounds like a straightforward variation on the classic height-of-tree problem, but there is a subtle twist. This problem, commonly known as Minimum Depth of Binary Tree on LeetCode, rewards you for choosing BFS over the DFS approach that works so well for maximum depth. Pick the wrong traversal and you either write buggy code or waste time exploring parts of the tree you never needed to visit.

TL;DR

Use BFS (level order traversal) with two queues. Process nodes level by level. The moment you encounter a leaf node, return the current depth. The two-queue approach cleanly tracks level boundaries without any extra counters or sentinel values.

Why This Problem Matters

Minimum depth is a gateway problem for understanding when BFS beats DFS. Most tree problems default to recursive DFS, but this one rewards you for thinking about traversal order. In an interview, choosing BFS here and explaining why signals that you understand the strengths and tradeoffs of each traversal strategy, not just how to write them.

Understanding the Problem

Given the root of a binary tree, return the minimum depth. The minimum depth is the smallest number of node traversals needed to reach a leaf node, starting at the root.

In this tree, node 7 is a leaf at level 2. Nodes 4 and 5 are leaves at level 3. The minimum depth is 2, because we only need to traverse two nodes (root 1, then 7) to reach the nearest leaf.

minDepth(1 7 3 # # 4 5) -> 2

Edge Cases

1. Null root: Return 0. An empty tree has no depth.
2. Single node: The root itself is a leaf. Return 1.

3. Skewed tree: Every node has only one child. The minimum depth equals the total number of nodes, because the only leaf is at the bottom.

Solution Approach

Since we want the minimum depth, we should stop searching as soon as we find the first leaf. BFS processes nodes level by level, so the first leaf it encounters is guaranteed to be at the shallowest depth. DFS would need to explore the entire tree before it could confirm which leaf is closest to the root.

The two-queue BFS approach works like this:

1. Start with the root in the current-level queue and set depth to 1.
2. Dequeue a node. If it is a leaf, return depth immediately.
3. Otherwise, enqueue its non-null children into the next-level queue.
4. When the current-level queue is empty, you have finished one level. Increment depth, swap the queues, and continue.

Here is the BFS trace for the example tree [1, 7, 3, #, #, 4, 5]:

BFS finds the leaf node 7 at level 2 and returns immediately. It never needs to process nodes 4 or 5.

Implementation

Prefer a different language? Jump to solutions in all 14 languages.

import java.util.Deque;
import java.util.LinkedList;

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

    int depth = 1;
    Deque<TreeNode> curLevelQueue = new LinkedList<>();
    Deque<TreeNode> nextLevelQueue = new LinkedList<>();
    curLevelQueue.offer(root);

    while (!curLevelQueue.isEmpty()) {
      TreeNode node = curLevelQueue.poll();

      if (node.left == null && node.right == null) return depth;

      if (node.left != null) nextLevelQueue.offer(node.left);
      if (node.right != null) nextLevelQueue.offer(node.right);

      if (curLevelQueue.isEmpty()) {
        depth++;
        curLevelQueue = nextLevelQueue;
        nextLevelQueue = new LinkedList<>();
      }
    }

    return depth;
  }
}

Walking through the key decisions:

1. Null check first: If the tree is empty, there is nothing to traverse. Return 0.
2. Depth starts at 1: The root is at depth 1 (we count nodes, not edges).
3. Two queues: curLevelQueue holds all nodes at the current depth. nextLevelQueue collects their children. When curLevelQueue drains, we know we have finished one level.
4. Early return on leaf: The first time we see a node with no children, we return immediately. This is the core advantage of BFS for this problem.

Dry Run

For the test case tree [1, 2, 3, #, #, 4, 5]:

• Level 1: Process node 1. Not a leaf (has children 2 and 3). Add both to next queue.
• Level 2: Process node 2. It is a leaf (no children). Return depth = 2.

Node 3 and its children are never visited. BFS saved us from exploring the deeper right subtree.

Complexity Analysis

Time: O(n). In the worst case (a completely balanced tree or a skewed tree), BFS visits every node. In the best case, it stops early when it finds a leaf at a shallow level. For a balanced tree of height h, BFS visits roughly 2^h - 1 nodes before reaching the leaf level, which is about n/2.

Space: O(n). The queues hold at most all nodes at one level. In a balanced binary tree, the widest level contains about n/2 nodes. For a skewed tree, each level has one node, so space is O(1).

Balanced Tree Example

In a balanced tree with 7 nodes, the first leaves appear at level 3. BFS visits all 3 levels (7 nodes total). The widest level (level 3) holds 4 nodes in the queue simultaneously.

Common Pitfalls

1. Using DFS and taking min(left, right) + 1 naively: If a node has only one child, the missing child returns depth 0. Taking the minimum gives you 1 (root + missing child), which is wrong because the missing child is not a leaf. You must check whether each child exists before recursing.

2. Starting depth at 0 instead of 1: The root node counts as depth 1. If you start at 0 and increment after finding a leaf, you will be off by one.

3. Forgetting the null root check: If root is null, accessing its fields will throw a NullPointerException. Always guard against this before initializing queues.

4. Using a single queue with a size counter: This works but is slightly more error-prone. The two-queue approach is cleaner because level boundaries are explicit, not implicit.

Interview Tips

When presenting this solution:

• State upfront that BFS is the right choice because it finds the shallowest leaf first. This shows you are thinking about the problem before coding.
• Draw the two-queue mechanism for a small tree. Interviewers appreciate candidates who can explain the level-boundary tracking.
• Mention the DFS pitfall (single-child nodes returning incorrect depth). This demonstrates you considered alternatives and understand why BFS is better here.
• If the interviewer asks for optimization, point out that BFS already provides early termination. The only improvement would be using a single queue with a size counter, which saves one object allocation per level but adds bookkeeping.

Key Takeaways

• BFS is the natural fit for minimum depth because it finds the shallowest leaf without exploring deeper levels unnecessarily.
• The two-queue pattern is a clean way to track level boundaries in BFS. When the current queue empties, you have finished a level.
• Always handle the null root edge case. Always start depth at 1 (counting nodes, not edges).
• Naive recursive DFS fails on nodes with only one child. If you use DFS, you must add extra checks to avoid counting non-leaf null nodes.
• This problem teaches you to pick the right traversal for the job. Most tree problems use DFS by default, but minimum depth is a clear case where BFS is more elegant and efficient.

Practice and Related Problems

Once you are comfortable with minimum depth, try these natural progressions:

• Height of a binary tree (DFS is the better fit here, a nice contrast)
• Binary tree level order traversal (the same BFS pattern, but collecting all levels)
• Symmetric tree (level-based comparison)

This problem and hundreds of others are available on Firecode, where spaced repetition ensures you internalize patterns like BFS and level order traversal rather than just memorizing solutions. Understanding when to use BFS vs. DFS is a skill that pays off across dozens of tree and graph problems.

Solutions in Other Languages

Python

from collections import deque

class Solution:
    def min_depth(self, root):
        if root is None:
            return 0

        depth = 1
        cur_level_queue, next_level_queue = deque(), deque()
        cur_level_queue.append(root)

        while len(cur_level_queue) > 0:
            node = cur_level_queue.popleft()

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

            if node.left is not None:
                next_level_queue.append(node.left)
            if node.right is not None:
                next_level_queue.append(node.right)

            if len(cur_level_queue) == 0:
                depth += 1
                cur_level_queue = next_level_queue
                next_level_queue = deque()

        return depth

JavaScript

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

    let depth = 1;
    let curLevelQueue = new Queue(), nextLevelQueue = new Queue();
    curLevelQueue.enqueue(root);

    while (curLevelQueue.nonEmpty()) {
      const node = curLevelQueue.dequeue();

      if (node.left === null && node.right === null) return depth;

      if (node.left !== null) nextLevelQueue.enqueue(node.left);
      if (node.right !== null) nextLevelQueue.enqueue(node.right);

      if (curLevelQueue.isEmpty()) {
        depth++;
        curLevelQueue = nextLevelQueue;
        nextLevelQueue = new Queue();
      }
    }

    return depth;
  }
}

TypeScript

class Solution {
  minDepth(root: TreeNode | null): number {
    if (root === null) return 0;

    let depth = 1;
    let curLevelQueue = new Queue<TreeNode>();
    let nextLevelQueue = new Queue<TreeNode>();
    curLevelQueue.offer(root);

    while (!curLevelQueue.isEmpty()) {
      const node = curLevelQueue.poll()!;

      if (node.left === null && node.right === null) return depth;

      if (node.left !== null) nextLevelQueue.offer(node.left);
      if (node.right !== null) nextLevelQueue.offer(node.right);

      if (curLevelQueue.isEmpty()) {
        depth++;
        curLevelQueue = nextLevelQueue;
        nextLevelQueue = new Queue<TreeNode>();
      }
    }

    return depth;
  }
}

C++

#include <queue>

class Solution {
public:
  int minDepth(TreeNode *root) {
    if (root == nullptr) return 0;

    int depth = 1;
    std::queue<TreeNode *> curLevelQueue, nextLevelQueue;
    curLevelQueue.push(root);

    while (!curLevelQueue.empty()) {
      TreeNode *node = curLevelQueue.front();
      curLevelQueue.pop();

      if (node->left == nullptr && node->right == nullptr) return depth;

      if (node->left != nullptr) nextLevelQueue.push(node->left);
      if (node->right != nullptr) nextLevelQueue.push(node->right);

      if (curLevelQueue.empty()) {
        depth++;
        curLevelQueue = std::queue<TreeNode *>(nextLevelQueue);
        nextLevelQueue = std::queue<TreeNode *>();
      }
    }

    return depth;
  }
};

Go

package solution

func (s *Solution) MinDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    depth := 1
    curLevelQueue, nextLevelQueue := NewQueue(), NewQueue()
    curLevelQueue.Offer(root)

    for !curLevelQueue.IsEmpty() {
        node := curLevelQueue.Poll().(*TreeNode)

        if node.Left == nil && node.Right == nil {
            return depth
        }

        if node.Left != nil {
            nextLevelQueue.Offer(node.Left)
        }
        if node.Right != nil {
            nextLevelQueue.Offer(node.Right)
        }

        if curLevelQueue.IsEmpty() {
            depth++
            curLevelQueue = nextLevelQueue
            nextLevelQueue = NewQueue()
        }
    }

    return depth
}

Scala

import scala.collection.mutable

class Solution {
  def minDepth(root: TreeNode): Int = {
    if (root == null) return 0

    var depth = 1
    var curLevelQueue = mutable.Queue[TreeNode]()
    var nextLevelQueue = mutable.Queue[TreeNode]()
    curLevelQueue.enqueue(root)

    while (curLevelQueue.nonEmpty) {
      val node = curLevelQueue.dequeue

      if (node.left == null && node.right == null) return depth

      if (node.left != null) nextLevelQueue.enqueue(node.left)
      if (node.right != null) nextLevelQueue.enqueue(node.right)

      if (curLevelQueue.isEmpty) {
        depth += 1
        curLevelQueue = nextLevelQueue
        nextLevelQueue = mutable.Queue[TreeNode]()
      }
    }

    depth
  }
}

Kotlin

import java.util.Deque
import java.util.LinkedList

class Solution {
    fun minDepth(root: TreeNode?): Int {
        if (root == null) return 0

        var depth = 1
        var curLevelQueue: Deque<TreeNode> = LinkedList()
        var nextLevelQueue: Deque<TreeNode> = LinkedList()
        curLevelQueue.offer(root)

        while (!curLevelQueue.isEmpty()) {
            val node = curLevelQueue.poll()

            if (node.left == null && node.right == null) return depth

            if (node.left != null) nextLevelQueue.offer(node.left)
            if (node.right != null) nextLevelQueue.offer(node.right)

            if (curLevelQueue.isEmpty()) {
                depth++
                curLevelQueue = nextLevelQueue
                nextLevelQueue = LinkedList()
            }
        }

        return depth
    }
}

Swift

class Solution {
    func minDepth(_ root: TreeNode?) -> Int {
        if root == nil { return 0 }

        var depth = 1
        var curLevelQueue: [TreeNode] = [root!]
        var nextLevelQueue: [TreeNode] = []

        while !curLevelQueue.isEmpty {
            let node = curLevelQueue.removeFirst()

            if node.left == nil && node.right == nil { return depth }

            if node.left != nil { nextLevelQueue.append(node.left!) }
            if node.right != nil { nextLevelQueue.append(node.right!) }

            if curLevelQueue.isEmpty {
                depth += 1
                curLevelQueue = nextLevelQueue
                nextLevelQueue = []
            }
        }

        return depth
    }
}

Rust

use std::collections::VecDeque;

impl Solution {
    pub fn min_depth(&self, root: Option<Box<TreeNode>>) -> i32 {
        if root.is_none() {
            return 0;
        }

        let mut depth = 1;
        let mut cur_level_queue: VecDeque<Box<TreeNode>> = VecDeque::new();
        let mut next_level_queue: VecDeque<Box<TreeNode>> = VecDeque::new();
        cur_level_queue.push_back(root.unwrap());

        while let Some(node) = cur_level_queue.pop_front() {
            if node.left.is_none() && node.right.is_none() {
                return depth;
            }

            if let Some(left) = node.left {
                next_level_queue.push_back(left);
            }
            if let Some(right) = node.right {
                next_level_queue.push_back(right);
            }

            if cur_level_queue.is_empty() {
                depth += 1;
                cur_level_queue = next_level_queue;
                next_level_queue = VecDeque::new();
            }
        }

        depth
    }
}

C#

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

        var depth = 1;
        var curLevelQueue = new Queue<TreeNode>();
        var nextLevelQueue = new Queue<TreeNode>();
        curLevelQueue.Enqueue(root);

        while (curLevelQueue.Count > 0) {
            var node = curLevelQueue.Dequeue();

            if (node.left == null && node.right == null) return depth;

            if (node.left != null) nextLevelQueue.Enqueue(node.left);
            if (node.right != null) nextLevelQueue.Enqueue(node.right);

            if (curLevelQueue.Count == 0) {
                depth++;
                curLevelQueue = nextLevelQueue;
                nextLevelQueue = new Queue<TreeNode>();
            }
        }

        return depth;
    }
}

Dart

import 'dart:collection';

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

    int depth = 1;
    Queue<TreeNode> curLevelQueue = Queue();
    Queue<TreeNode> nextLevelQueue = Queue();
    curLevelQueue.add(root);

    while (curLevelQueue.isNotEmpty) {
      TreeNode node = curLevelQueue.removeFirst();

      if (node.left == null && node.right == null) return depth;

      if (node.left != null) nextLevelQueue.add(node.left!);
      if (node.right != null) nextLevelQueue.add(node.right!);

      if (curLevelQueue.isEmpty) {
        depth++;
        curLevelQueue = nextLevelQueue;
        nextLevelQueue = Queue();
      }
    }

    return depth;
  }
}

PHP

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

        $depth = 1;
        $curLevelQueue = [$root];
        $nextLevelQueue = [];

        while (!empty($curLevelQueue)) {
            $node = array_shift($curLevelQueue);

            if ($node->left === null && $node->right === null) return $depth;

            if ($node->left !== null) $nextLevelQueue[] = $node->left;
            if ($node->right !== null) $nextLevelQueue[] = $node->right;

            if (empty($curLevelQueue)) {
                $depth++;
                $curLevelQueue = $nextLevelQueue;
                $nextLevelQueue = [];
            }
        }

        return $depth;
    }
}

Ruby

class Solution
  def min_depth(root)
    return 0 if root.nil?

    depth = 1
    cur_level_queue = [root]
    next_level_queue = []

    until cur_level_queue.empty?
      node = cur_level_queue.shift

      return depth if node.left.nil? && node.right.nil?

      next_level_queue.push(node.left) unless node.left.nil?
      next_level_queue.push(node.right) unless node.right.nil?

      if cur_level_queue.empty?
        depth += 1
        cur_level_queue = next_level_queue
        next_level_queue = []
      end
    end

    depth
  end
end