111. Minimum Depth of Binary Tree
Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 39.8%
Problem Breakdown
The problem requires finding 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 node is one that has no children.
Inputs:
root: The root node of the binary tree.
Outputs:
- An integer representing the minimum depth of the binary tree.
Implicit Constraints or Tricky Edge Cases:
- Empty Tree: If the input tree is empty (
rootisNone), the minimum depth should be 0. - Single Node Tree: A tree with only one node (the root) has a minimum depth of 1.
- Unbalanced Trees: The tree might be unbalanced, meaning one subtree could be significantly deeper than the other.
Intuition
A brute-force approach would involve traversing all paths from the root to leaf nodes and keeping track of the shortest path length. This approach is inefficient because it explores all possible paths, leading to a time complexity of O(n), where n is the number of nodes in the tree.
The key insight is that we can optimize this by using a breadth-first search (BFS) strategy. BFS naturally finds the shortest path in an unweighted graph or tree structure, as it explores nodes level by level. This approach ensures that we find the minimum depth more efficiently.
Approach
- Check for Empty Tree: If the root is
None, return 0 immediately. - Initialize Queue: Use a queue to facilitate BFS. Each element in the queue will be a tuple containing a node and its current depth.
- Breadth-First Search:
- Start by adding the root node with an initial depth of 1 to the queue.
- While the queue is not empty, process each node:
- Dequeue the front element to get the current node and its depth.
- If the current node is a leaf (i.e., it has no left or right children), return the current depth as this is the minimum depth.
- Otherwise, enqueue the left child with an incremented depth if it exists.
- Enqueue the right child with an incremented depth if it exists.
- Return Result: The function will return when a leaf node is encountered, ensuring that the minimum depth is found.
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the tree. This is because each node is visited once.
- Space Complexity: O(n) in the worst case, where the queue contains all nodes at one level (e.g., a complete binary tree). In the best case, it’s O(1) if the tree is empty.
Solution
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def minDepth(root: TreeNode) -> int:
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
# Check if it's a leaf node
if not node.left and not node.right:
return depth
# Add children to the queue with incremented depth
if node.left:
queue.append((node.left, depth + 1))
if node.right:
queue.append((node.right, depth + 1))
Edge Cases Handled
- Empty Tree: The function returns 0 immediately if the root is
None. - Single Node Tree: The root itself is a leaf, so the function returns 1.
- Unbalanced Trees: BFS ensures that the shortest path to a leaf is found efficiently.