Minimum Depth of Binary Tree

Difficulty: Easy | Acceptance: 52.90% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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.

• Examples
• Constraints
• Approach 1: Recursive Depth-First Search
• Approach 2: Iterative Breadth-First Search
• Approach 3: Iterative Depth-First Search

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2
Explanation:
The minimum depth is 2, which is the path from root node (3) to leaf node (9).

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Explanation:
The minimum depth is 5, which is the path from root node (2) down to leaf node (6).

Constraints

The number of nodes in the tree is in the range [0, 10⁵].
-1000 <= Node.val <= 1000

Approach 1: Recursive Depth-First Search

Intuition We recursively traverse the tree. The key insight is that if a node has only one child, we must continue down that child; we cannot stop at the current node because it is not a leaf.

Steps

• If the root is null, return 0.
• If the node is a leaf (both left and right children are null), return 1.
• If the left child is null, recursively find the depth of the right subtree and add 1.
• If the right child is null, recursively find the depth of the left subtree and add 1.
• If both children exist, return the minimum of the depths of the left and right subtrees plus 1.

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        if not root.left:
            return 1 + self.minDepth(root.right)
        if not root.right:
            return 1 + self.minDepth(root.left)
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

Complexity

• Time: O(N), where N is the number of nodes in the tree. We visit every node once.
• Space: O(H), where H is the height of the tree. This is the space used by the recursion stack. In the worst case (skewed tree), it is O(N).
• Notes: Simple and elegant, but may cause stack overflow for very deep trees.

Approach 2: Iterative Breadth-First Search

Intuition Breadth-First Search (BFS) explores the tree level by level. The first leaf node we encounter during the traversal must be at the minimum depth, so we can return immediately.

Steps

• Initialize a queue with the root node and a depth of 1.
• While the queue is not empty:
  • Dequeue a node and its current depth.
  • If the node is a leaf, return the current depth.
  • Enqueue the left child with depth + 1 if it exists.
  • Enqueue the right child with depth + 1 if it exists.

from collections import deque

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        q = deque([(root, 1)])
        while q:
            node, depth = q.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                q.append((node.left, depth + 1))
            if node.right:
                q.append((node.right, depth + 1))
        return 0

Complexity

• Time: O(N), where N is the number of nodes. In the worst case, we might visit all nodes.
• Space: O(W), where W is the maximum width of the tree. This is generally more efficient than DFS for wide trees but can be O(N) in a perfect binary tree.
• Notes: This is often the most efficient approach for finding minimum depth because it stops as soon as it finds the first leaf.

Approach 3: Iterative Depth-First Search

Intuition We simulate the recursive DFS approach using an explicit stack. This avoids potential stack overflow issues associated with recursion on very deep trees.

Steps

• Initialize a stack with the root node and a depth of 1.
• Initialize a variable min_depth to infinity.
• While the stack is not empty:
  • Pop a node and its current depth.
  • If the node is a leaf, update min_depth with the minimum of min_depth and current depth.
  • Push the left child with depth + 1 if it exists.
  • Push the right child with depth + 1 if it exists.
• Return min_depth.

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        stack = [(root, 1)]
        min_depth = float('inf')
        while stack:
            node, depth = stack.pop()
            if not node.left and not node.right:
                min_depth = min(min_depth, depth)
            if node.left:
                stack.append((node.left, depth + 1))
            if node.right:
                stack.append((node.right, depth + 1))
        return min_depth

Complexity

• Time: O(N), where N is the number of nodes. We visit every node once.
• Space: O(H), where H is the height of the tree. The stack stores the path to the current node.
• Notes: Useful for avoiding recursion depth limits, though generally slower than BFS for this specific problem because it must traverse the entire tree in the worst case.