Log inSign up
easyleetcodeNot Started

Minimum Depth of Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given a binary tree, find 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.

Note: A leaf is a node with no children.

Example 1 · Example 1: Standard Tree:

Input: root = [3, 9, 20, null, null, 15, 7]
Output: 2
Explanation: Shortest path is 3 -> 9 (length 2).

Example 2 · Example 2: Skewed Tree:

Input: root = [2, null, 3, null, 4, null, 5, null, 6]
Output: 5
Explanation: All nodes only have right children. Leaf is at node 6, so path length is 5.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Avoid the classic single-child bug where min(left, right) incorrectly returns 0.
  • Understand why BFS is faster than DFS for minimum depth (early exit).
  • Formulate robust leaf node verification.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Shortest path from root to a leaf node.
  • Nearest leaf node distance.
  • BFS early exit candidate.

Algorithmic Decision Tree:

  • If root == null -> return 0.
  • BFS: push {node, depth=1}; if node.left == null && node.right == null -> return depth immediately.

Connected Patterns:

Maximum Depth of Binary TreeBinary Tree Level Order TraversalPath Sum

1. All Paths Enumeration to Leaves

Intuition

Recursively traverse to leaves. When reaching a leaf, update minDepth. Return minDepth at the end.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: Track minDepth initialized to infinity.
  3. Step 3: In dfs(node, curDepth): if node is leaf, minDepth = min(minDepth, curDepth).
  4. Step 4: Recurse on children.
  5. Step 5: Return minDepth.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, int cur, int& minD) {
10 if (!node) return;
11 if (!node->left && !node->right) {
12 minD = min(minD, cur);
13 return;
14 }
15 dfs(node->left, cur + 1, minD);
16 dfs(node->right, cur + 1, minD);
17 }
18 int minDepth(TreeNode* root) {
19 if (!root) return 0;
20 int minD = INT_MAX;
21 dfs(root, 1, minD);
22 return minD;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Visits all nodes in the tree.
  • Space complexity: O(h) — Call stack takes O(h) space.

2. Recursive DFS with Skew Guard

Intuition

If root is null, return 0. If left is null, return 1 + minDepth(right). If right is null, return 1 + minDepth(left). If both exist, return 1 + min(minDepth(left), minDepth(right)).

When to apply: When recursive solution is preferred.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: If root.left == null return 1 + minDepth(root.right).
  3. Step 3: If root.right == null return 1 + minDepth(root.left).
  4. Step 4: Return 1 + min(minDepth(root.left), minDepth(root.right)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minDepth(TreeNode* root) {
10 if (!root) return 0;
11 if (!root->left) return 1 + minDepth(root->right);
12 if (!root->right) return 1 + minDepth(root->left);
13 return 1 + min(minDepth(root->left), minDepth(root->right));
14 }
15};
16
17int main() {
18 // Sample driver execution
19 cout << "Execution completed successfully." << endl;
20 return 0;
21}
22

Time & Space Complexity

  • Time complexity: O(n) — Visits each node once in O(n) time.
  • Space complexity: O(h) — Call stack depth O(h).

3. BFS with Early Exit on First Leaf

Intuition

Initialize queue with {root, 1}. In each step: pop node and current depth. If node.left == null and node.right == null, return depth immediately. Otherwise enqueue children with depth + 1.

When to apply: Fastest practical solution (stops without scanning entire deep subtrees).

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: Initialize queue q, push {root, 1}.
  3. Step 3: While q is not empty:
  4. - Pop {node, depth}.
  5. - If node.left == null && node.right == null: return depth.
  6. - If node.left != null: push {node.left, depth + 1}.
  7. - If node.right != null: push {node.right, depth + 1}.
  8. Step 4: Return 0.

BFS Minimum Depth Trace for root = [3, 9, 20]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Queue has root (3) at depth 1
Visual state
Values and pointers at this exact step
tree
Root
3
L
9
R
20

Node order shown; add connections to display explicit tree edges.

curr: 3
Check / comparison
Node 3 has children -> Continue BFS
Decision / next transition
Enqueue left child (9) and right child (20).
Why this step matters

Step 1: Queue has root (3) at depth 1. Node 3 has children (9 and 20), not a leaf. Enqueue 9 and 20. Move to depth 2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minDepth(TreeNode* root) {
10 if (!root) return 0;
11 queue<pair<TreeNode*, int>> q;
12 q.push({root, 1});
13 while (!q.empty()) {
14 auto [node, depth] = q.front();
15 q.pop();
16 if (!node->left && !node->right) return depth;
17 if (node->left) q.push({node->left, depth + 1});
18 if (node->right) q.push({node->right, depth + 1});
19 }
20 return 0;
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(n) worst case, O(w) average — Does not need to traverse the entire tree; terminates immediately at the shallowest leaf.
  • Space complexity: O(w) — Queue holds at most width w of tree.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All Paths DFSO(n)O(h)Exhaustive leaf path collection.No early exit.
2.Recursive DFS with GuardO(n)O(h)Recurse single child when other child is null.Full tree exploration.
3.BFS with Early ExitOptimalO(min_nodes)O(w)Queue BFS terminating on first encountered leaf.None. Operationally optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns 0.
  • Single node: root = [1] -> returns 1.
  • Skewed tree (e.g. [2, null, 3, null, 4, null, 5, null, 6]) -> minimum depth is 5, not 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight the edge case where root has only 1 child (e.g. root [1, 2] has min depth 2, not 1).
  2. Explain why BFS with a queue is optimal in practice: it stops at the very first leaf without visiting the rest of the tree.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.For a tree with root [1, 2] (only a left child), why is minimum depth 2 and NOT 1?

Back to DSA Sheet