Dare2Solve
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).
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.
Base Case:
null
), return 0
as the minimum depth.Breadth-First Search (BFS):
level
variable set to 1
, representing the current depth of the tree.levelSize
) and process each node in the queue.null
). If a leaf node is found, return the current level
as the minimum depth.level
variable after processing all nodes at the current level.Return Result:
level
at that point will be the minimum depth of the tree.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.
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.
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
std::queue<TreeNode*> 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;
}
};
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
class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> 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;
}
}
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++;
}
}