
Description
The problem is to find the minimum depth of a binary tree. The minimum depth is defined as the number of nodes along the shortest path from the root node down to the nearest leaf node (a leaf is a node with no children).
Intuition
The minimum depth of a binary tree can be determined using a breadth-first search (BFS) approach. Since BFS explores the tree level by level, the first time it encounters a leaf node, it can immediately return the current depth as the minimum depth. This ensures that the shortest path to a leaf node is found efficiently.
Approach
- Base Case:
- If the tree is empty (i.e., the root is
null
), return0
as the minimum depth. - Breadth-First Search (BFS):
- Initialize a queue and add the root node to it. Start with a
level
variable set to1
, representing the current depth of the tree. - Use a loop to process nodes level by level. For each level, determine the number of nodes (levelSize
) and process each node in the queue. - For each node, check if it is a leaf node (both left and right children arenull
). If a leaf node is found, return the currentlevel
as the minimum depth. - If the node has left or right children, add them to the queue for processing in the next level. - Increment thelevel
variable after processing all nodes at the current level. - Return Result:
- The loop will eventually find a leaf node, and the
level
at that point will be the minimum depth of the tree.
Complexity
Time Complexity:
The time complexity is (O(n)), where n
is the number of nodes in the tree. In the worst case, all nodes are visited once.
Space Complexity:
The space complexity is (O(n)), which is the maximum number of nodes that can be stored in the queue at any time. In the worst case, this could be proportional to the number of nodes at the bottom level of the tree, which is approximately (O(n)) for a complete binary tree.
Code
C++
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
std::queue queue;
queue.push(root);
int level = 1;
while (!queue.empty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode* node = queue.front();
queue.pop();
if (node->left == nullptr && node->right == nullptr) {
return level;
}
if (node->left != nullptr) {
queue.push(node->left);
}
if (node->right != nullptr) {
queue.push(node->right);
}
}
level++;
}
return level;
}
};
Python
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([root])
level = 1
while queue:
levelSize = len(queue)
for _ in range(levelSize):
node = queue.popleft()
if not node.left and not node.right:
return level
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
level += 1
return level
Java
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue queue = new LinkedList<>();
queue.add(root);
int level = 1;
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return level;
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
level++;
}
return level;
}
}
JavaScript
function minDepth(root) {
if (root === null) return 0;
let queue = [root];
let level = 1;
while (queue.length > 0) {
let levelSize = queue.length;
for (let i = 0; i < levelSize; i++) {
let node = queue.shift();
if (node.left === null && node.right === null) {
return level;
}
if (node.left !== null) {
queue.push(node.left);
}
if (node.right !== null) {
queue.push(node.right);
}
}
level++;
}
}