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.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
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.Hint 2
Handle the cases separately — no children (depth 1), one child (follow it), two children (take the smaller).
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
- If
rootis null, return 0. - Put
rooton a queue with depth 1. - Dequeue a node; if it has no children, return its depth.
- 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 0Java
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)