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:
Input: root = [3,9,20,null,null,15,7] Output: 2
Example 2:
Input: root = [2,null,3,null,4,null,5,null,6] Output: 5
Constraints:
[0, 105].-1000 <= Node.val <= 1000The goal of #111 Minimum Depth of Binary Tree is to determine the shortest distance from the root node to the nearest leaf node. A leaf node is defined as a node with no left or right children. The key challenge is correctly identifying leaf nodes while traversing the tree.
A common and efficient strategy is Breadth-First Search (BFS). Using a queue, traverse the tree level by level. The first time you encounter a leaf node, you can immediately return the current depth because BFS explores nodes in increasing depth order. This makes BFS very intuitive for this problem.
Another option is Depth-First Search (DFS) using recursion. For each node, compute the minimum depth of its left and right subtrees. However, special care is needed when one child is missing, since the path must continue through the existing subtree until a leaf is reached.
Both methods visit each node at most once, giving a time complexity of O(n), where n is the number of nodes in the tree.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(n) |
| Depth-First Search (Recursive) | O(n) | O(h) |
NeetCode
The BFS approach utilizes a queue to perform a level-order traversal of the tree. Each node is dequeued and checked if it is a leaf node. The level count is incremented each time a complete level is processed. The algorithm stops as soon as a leaf node is found, and the current level is returned as the minimum depth.
Time complexity is O(N), where N is the number of nodes, because each node is processed once. Space complexity is O(N) due to the storage requirements of the queue in the worst case (a complete/filled tree).
1#include <iostream>
2#include <queue>
3using namespace std;
4
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12int minDepth(TreeNode* root) {
13 if (!root) return 0;
14 queue<pair<TreeNode*, int>> q;
q.push({root, 1});
while (!q.empty()) {
TreeNode* node = q.front().first;
int depth = q.front().second;
q.pop();
if (!node->left && !node->right) return depth;
if (node->left) q.push({node->left, depth + 1});
if (node->right) q.push({node->right, depth + 1});
}
return 0;
}
This C++ solution uses the standard library queue to implement the BFS. Each node is stored in the queue along with its depth as a pair. The minimal depth is determined by the first leaf encountered during traversal.
In the DFS approach, we perform a pre-order traversal of the tree with recursive calls. The minimum depth is calculated by determining the shortest path from the root to any leaf node, where leaf nodes are identified as those without children.
Time complexity is O(N) as each node requires inspection to determine minimum depth. Space complexity can be O(N) in the case of skewed trees due to the recursive stack's depth, but typically O(log N) for balanced trees.
1using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
if (!root->left && !root->right) return 1;
int left = root->left ? minDepth(root->left) : INT_MAX;
int right = root->right ? minDepth(root->right) : INT_MAX;
return 1 + min(left, right);
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of binary tree traversal problems like Minimum Depth of Binary Tree frequently appear in technical interviews at FAANG and other top companies. They test understanding of tree traversal strategies such as BFS and DFS.
If one child is null, taking the minimum would incorrectly return zero and ignore the valid subtree. Instead, the algorithm must continue through the non-null child until a leaf node is reached. Handling these edge cases is important for correctness.
The optimal approach is typically Breadth-First Search (BFS). Since BFS explores nodes level by level, the first leaf node encountered represents the minimum depth. This allows the algorithm to terminate early without exploring the entire tree.
A queue is commonly used for the BFS approach because it supports level-order traversal of the binary tree. For DFS solutions, recursion or an explicit stack can be used to explore paths down the tree.
This C++ solution recurses through each node's children until a leaf is reached, at which point it returns the path's length. The algorithm compares the depth of the left and right sub-trees at each node, selecting the lesser depth.