LeetCode 111 - Minimum Depth of Binary Tree
The problem asks us to determine the minimum depth of a binary tree. In other words, given the root of a binary tree, we want to find the shortest path from the root node down to the nearest leaf node.
Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Solution
Problem Understanding
The problem asks us to determine the minimum depth of a binary tree. In other words, given the root of a binary tree, we want to find the shortest path from the root node down to the nearest leaf node. A leaf node is explicitly defined as a node with no children, meaning both its left and right pointers are null.
The input is a binary tree, which may be empty, and the output is an integer representing the minimum depth. For example, a tree with only one node has a minimum depth of 1 because the root itself is a leaf. The constraints indicate that the tree may have up to 100,000 nodes, so an inefficient solution that repeatedly traverses the entire tree could be too slow. Node values are in the range [-1000, 1000], but the values themselves do not impact the computation of depth.
Important edge cases include an empty tree (minimum depth should be 0), a tree where each node has only one child (effectively a linked list, where the minimum depth equals the total number of nodes), and trees where the root has one null child and one non-null child. A naive implementation that calculates both left and right depths without handling null children carefully could mistakenly count the depth of non-existent paths as zero.
Approaches
A brute-force approach is to use a recursive depth-first search (DFS). We would recursively compute the minimum depth for both the left and right subtrees and take the smaller value, adding one for the current node. This works in principle but has a subtle issue: if one of the children is null, we cannot take the minimum of zero and the other depth because that would underestimate the depth. We must treat null children differently to avoid this mistake.
A more optimal approach uses a breadth-first search (BFS) traversal. The key insight is that BFS naturally explores the tree level by level. As soon as we encounter the first leaf node, we can return its depth immediately, because BFS guarantees it is the shallowest leaf. This avoids traversing the entire tree and is more efficient, particularly for unbalanced trees.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force DFS | O(n) | O(h) | Recursively compute min depth for each subtree; h is tree height |
| Optimal BFS | O(n) | O(w) | Level-order traversal using a queue; w is max width of tree |
Algorithm Walkthrough
- Check if the root is null. If it is, return 0 immediately since the tree is empty.
- Initialize a queue and add the root node along with its depth as a tuple
(node, depth). - While the queue is not empty, remove the front node and its depth from the queue.
- Check if the current node is a leaf (both left and right children are null). If it is, return its depth immediately. This is the minimum depth because BFS guarantees that we encounter shallow nodes first.
- If the node has a left child, add it to the queue with a depth incremented by 1.
- If the node has a right child, add it to the queue with a depth incremented by 1.
- Continue until the queue is empty. The first leaf encountered gives the minimum depth.
Why it works: BFS ensures that nodes are visited level by level. The first leaf node we encounter must be at the minimum depth because all shallower nodes would have been visited already. This guarantees correctness and efficiency.
Python Solution
from collections import deque
from typing import Optional
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
if not node.left and not node.right:
return depth
if node.left:
queue.append((node.left, depth + 1))
if node.right:
queue.append((node.right, depth + 1))
The Python implementation starts by handling the empty tree case. We use a deque as a queue to maintain nodes along with their depths. The BFS ensures that as soon as a leaf is found, we immediately return its depth, which avoids unnecessary exploration of deeper nodes. The tuple (node, depth) allows tracking the current depth without recomputation.
Go Solution
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
type NodeDepth struct {
node *TreeNode
depth int
}
queue := []NodeDepth{{root, 1}}
for len(queue) > 0 {
current := queue[0]
queue = queue[1:]
if current.node.Left == nil && current.node.Right == nil {
return current.depth
}
if current.node.Left != nil {
queue = append(queue, NodeDepth{current.node.Left, current.depth + 1})
}
if current.node.Right != nil {
queue = append(queue, NodeDepth{current.node.Right, current.depth + 1})
}
}
return 0
}
In Go, we use a slice to implement the queue and a struct NodeDepth to keep track of nodes and their depths. Unlike Python, Go requires explicit handling of nil pointers, but the logic mirrors the BFS approach in Python. Appending to a slice provides queue behavior with O(1) amortized complexity.
Worked Examples
Example 1: [3,9,20,null,null,15,7]
| Queue State | Action |
|---|---|
| [(3,1)] | pop 3, add 9 and 20 to queue |
| [(9,2),(20,2)] | pop 9, it is a leaf → return 2 |
Example 2: [2,null,3,null,4,null,5,null,6]
| Queue State | Action |
|---|---|
| [(2,1)] | pop 2, add 3 |
| [(3,2)] | pop 3, add 4 |
| [(4,3)] | pop 4, add 5 |
| [(5,4)] | pop 5, add 6 |
| [(6,5)] | pop 6, it is a leaf → return 5 |
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Every node is visited at most once in BFS |
| Space | O(w) | Queue holds at most the maximum width of the tree |
The space complexity depends on the maximum number of nodes at any level, which can be much smaller than n for a balanced tree but can approach n for a very wide tree.
Test Cases
# Empty tree
assert Solution().minDepth(None) == 0
# Single node
root = TreeNode(1)
assert Solution().minDepth(root) == 1
# Balanced tree
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
assert Solution().minDepth(root) == 2
# Linked-list like tree (all right children)
root = TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5, None, TreeNode(6)))))
assert Solution().minDepth(root) == 5
# Left child only
root = TreeNode(1, TreeNode(2))
assert Solution().minDepth(root) == 2
| Test | Why |
|---|---|
| Empty tree | Ensures empty input returns 0 |
| Single node | Validates base case of one-node tree |
| Balanced tree | Tests normal BFS finding shallow leaf |
| Right-skewed tree | Ensures correct depth in unbalanced tree |
| Left child only | Confirms handling of single child nodes |
Edge Cases
One important edge case is an empty tree. A naive implementation that assumes the root exists may throw an exception. Our solution explicitly checks if not root or if root == nil to return 0.
Another edge case is a skewed tree, where all nodes are either left or right children. A DFS implementation might fail if it simply takes the minimum of left and right depths without considering that one child is null. Our BFS approach handles this naturally by only adding non-null children to the queue.
A third edge case is when the root has one null child and one non-null child. If the algorithm incorrectly treats a null child as depth zero in DFS, it would underestimate the minimum depth. In BFS, this is automatically handled because null children are never enqueued, and the first leaf encountered gives the correct depth.