Minimum Depth of Binary Tree

Easy
1865.

Minimum Depth of Binary Tree

Minimum Depth of Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

Given the root of a binary tree, return its minimum depth: the number of nodes on the shortest path from the root down to the nearest leaf. A leaf is a node with no children. An empty tree has minimum depth 0.

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
2
Explanation
9 is a leaf, so the path 3 → 9 of two nodes is the shortest.

Example 2

Input
root = [2,null,3,null,4,null,5,null,6]
Output
5
Explanation
The tree is one chain; the only leaf is 6, five nodes down. The root's missing left child is not a leaf.

Example 3

Input
root = []
Output
0

Constraints

  • The number of nodes in the tree is in the range [0, 10^5]
  • -1000 <= Node.val <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Depth of Binary Tree — Problem & Solution

Minimum Depth of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Minimum Depth of Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

Problem statement

Given the root of a binary tree, return its minimum depth: the number of nodes on the shortest path from the root down to the nearest leaf. A leaf is a node with no children. An empty tree has minimum depth 0.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: 2
Explanation: 9 is a leaf, so the path 3 → 9 of two nodes is the shortest.

Example 2

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Explanation: The tree is one chain; the only leaf is 6, five nodes down. The root's missing left child is not a leaf.

Example 3

Input: root = []
Output: 0

Constraints

  • The number of nodes in the tree is in the range [0, 10^5]
  • -1000 <= Node.val <= 1000

Hints for Minimum Depth of Binary Tree

  1. Hint 1

    This is not 1 + min(left, right): a node with one child is not a leaf, so its missing side must not count as depth 0.

  2. Hint 2

    Handle the cases separately — no children (depth 1), one child (follow it), two children (take the smaller).

  3. Hint 3

    A breadth-first search can stop at the first leaf it meets, which is the shallowest one.

How to solve Minimum Depth of Binary Tree

The answer is the depth of the shallowest leaf. A level-by-level BFS meets leaves in order of depth, so the first leaf it dequeues gives the answer — and it never explores below that level.

Approach

  1. If root is null, return 0.
  2. Put root on a queue with depth 1.
  3. Dequeue a node; if it has no children, return its depth.
  4. Otherwise enqueue each existing child with depth + 1, and repeat.

Why it works

BFS dequeues every node at depth d before any node at depth d + 1, so the first leaf dequeued is at the smallest depth any leaf has. A recursive alternative must treat a one-child node as having only that child — taking the min with an empty side would report a path that ends at a non-leaf.

Complexity

  • Time — O(n) in the worst case, and only the levels above the shallowest leaf with BFS
  • Space — O(width) for the queue

Pitfalls

  • 1 + min(minDepth(left), minDepth(right)) returns 1 for [1,2], but the root is not a leaf there — the answer is 2.
  • An empty tree is 0, a single node is 1.

Reference solution

Python

from typing import Optional
from collections import deque

def minDepth(root: Optional[TreeNode]) -> int:
    if root is None:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, d = queue.popleft()
        if node.left is None and node.right is None:
            return d
        if node.left is not None:
            queue.append((node.left, d + 1))
        if node.right is not None:
            queue.append((node.right, d + 1))
    return 0

Java

public static int minDepth(TreeNode root) {
    if (root == null) return 0;
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    int depth = 1;
    while (!queue.isEmpty()) {
        for (int k = queue.size(); k > 0; k--) {
            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;
}

C++

int minDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int depth = 1;
    while (!q.empty()) {
        for (int k = (int) q.size(); k > 0; k--) {
            TreeNode* node = q.front();
            q.pop();
            if (!node->left && !node->right) return depth;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        depth++;
    }
    return depth;
}

JavaScript

var minDepth = function(root) {
    if (root === null) return 0;
    var level = [root], depth = 1;
    for (;;) {
        var next = [];
        for (var i = 0; i < level.length; i++) {
            var node = level[i];
            if (node.left === null && node.right === null) return depth;
            if (node.left !== null) next.push(node.left);
            if (node.right !== null) next.push(node.right);
        }
        level = next;
        depth++;
    }
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)