LeetCode 111: Minimum Depth of Binary Tree Solution in Python Explained

Problem Statement

In LeetCode 111, you’re given the root of a binary tree. Your task is to return its minimum depth, defined as the number of nodes along the shortest path from the root to a leaf node (a node with no children). This contrasts with balance validation like LeetCode 110: Balanced Binary Tree, focusing on the shortest path rather than height differences.

Constraints

• Number of nodes: 0 <= n <= 10^5
• Node values: -1000 <= Node.val <= 1000

Example

Let’s see some cases:

Copy codeInput: root = [3,9,20,null,null,15,7]
      3
     / \
    9  20
       / \
      15  7
Output: 2
Explanation: Shortest path: 3->9 (2 nodes).

Copy codeInput: root = [2,null,3,null,4,null,5,null,6]
      2
       \
        3
         \
          4
           \
            5
             \
              6
Output: 5
Explanation: Only path: 2->3->4->5->6 (5 nodes).

Copy codeInput: root = []
Output: 0
Explanation: Empty tree, depth 0.

These examples show we’re finding the shortest root-to-leaf path.

Understanding the Problem

How do you solve LeetCode 111: Minimum Depth of Binary Tree in Python? Take root = [3,9,20,null,null,15,7]. We need the minimum depth—path 3->9 has 2 nodes, shorter than 3->20->15 or 3->20->7 (3 nodes), so return 2. For [2,null,3,null,4,null,5,null,6], the only path has 5 nodes. This isn’t a level-order traversal like LeetCode 107: Binary Tree Level Order Traversal II; it’s about finding the shortest path to a leaf. We’ll use: 1. Recursive DFS: O(n) time, O(h) space—our best solution. 2. Queue-Based BFS: O(n) time, O(w) space—an alternative.

Let’s dive into the best solution.

Best Solution: Recursive DFS Approach

Explanation

Recursive DFS calculates the minimum depth by recursively computing the depth to each leaf, returning the minimum of left and right subtree depths for nodes with both children, or the depth of the only child for nodes with one child. It’s the best solution due to its O(n) time complexity, simplicity, and efficient handling of edge cases like unbalanced trees, ensuring we find the shortest path without extra overhead.

For [3,9,20,null,null,15,7]:

• Leaf 9: Depth 1.
• Leaf 15, 7: Depth 2.
• Node 20: Min(2, 2) = 2.
• Node 3: Min(1, 2) = 1 from 9, total 2.
• Result: 2.

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: root = [3,9,20,null,null,15,7]

Goal: Return 2.

• Start: minDepth(3).
• Step 1: root = 3.
• Left: minDepth(9).
• Leaf 9, no children, return 1.
• Right: minDepth(20).
• Left: minDepth(15) → 1.
• Right: minDepth(7) → 1.
• 20: Both children, min(1, 1) + 1 = 2.
• 3: Both children, min(1, 2) + 1 = 2.
• Finish: Return 2.

Example 2: root = [2,null,3,null,4,null,5,null,6]

Goal: Return 5.

• Start: minDepth(2).
• Step 1: root = 2.
• Left: None → 0.
• Right: minDepth(3).
• Left: None → 0.
• Right: minDepth(4).
• Left: None → 0.
• Right: minDepth(5).
• Left: None → 0.
• Right: minDepth(6) → 1.
• 5: Right only, 1 + 1 = 2.
• 4: Right only, 2 + 1 = 3.
• 3: Right only, 3 + 1 = 4.
• 2: Right only, 4 + 1 = 5.
• Finish: Return 5.

Example 3: root = []

Goal: Return 0.

• Start: minDepth(None).
• Step 1: Null root, return 0.
• Finish: Return 0.

How the Code Works (Recursive DFS) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDepth(root: TreeNode) -> int:
    # Line 1: Base case - check if root is null
    if not root:
        # If root is None (e.g., empty tree), depth is 0
        return 0

    # Line 2: Check if leaf node
    if not root.left and not root.right:
        # If no children (e.g., leaf like 9), depth is 1
        return 1

    # Line 3: Handle single-child nodes
    if not root.left:
        # If only right child exists (e.g., 2 in skewed tree), recurse right
        return 1 + minDepth(root.right)
        # Adds 1 to right subtree’s min depth (e.g., 1 + 4 = 5 for 2)

    if not root.right:
        # If only left child exists (e.g., hypothetical), recurse left
        return 1 + minDepth(root.left)
        # Adds 1 to left subtree’s min depth

    # Line 4: Compute minimum depth for nodes with both children
    left_depth = minDepth(root.left)
    # Recursively gets left min depth (e.g., 9 → 1)

    right_depth = minDepth(root.right)
    # Recursively gets right min depth (e.g., 20 → 2)

    # Line 5: Return minimum depth including current node
    return 1 + min(left_depth, right_depth)
    # Adds 1 for current node, takes min of subtrees
    # e.g., root=3, left=1, right=2 → 1 + min(1, 2) = 2

This detailed breakdown clarifies how recursive DFS efficiently computes the minimum depth.

Alternative: Queue-Based BFS Approach

Explanation

Queue-Based BFS processes the tree level-by-level, tracking each node’s depth in the queue, and returns the depth of the first leaf encountered. It’s a practical alternative, using breadth-first traversal to find the shortest path quickly, especially effective for unbalanced trees.

For [3,9,20,null,null,15,7]:

• Level 1: [3].
• Level 2: [9,20], 9 is leaf, return 2.
• Stops early.

Step-by-Step Example (Alternative)

For [3,9,20,null,null,15,7]:

• Start: queue = [(3, 1)].
• Step 1: Pop (3,1), add (9,2), (20,2).
• Step 2: Pop (9,2), leaf, return 2.
• Finish: Return 2.

For [2,null,3,null,4,null,5,null,6]:

• Step: Process all levels, leaf 6 at depth 5.
• Finish: Return 5.

How the Code Works (BFS)

Copy codefrom collections import deque

def minDepthBFS(root: 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))
    return 0  # Unreachable due to constraints

Complexity

• Recursive DFS:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Queue-Based BFS:
• Time: O(n) – worst case visits all nodes.
• Space: O(w) – queue size, w = max width.

Efficiency Notes

Recursive DFS is the best solution with O(n) time and O(h) space, offering simplicity and efficiency across all tree shapes—Queue-Based BFS matches time complexity with O(w) space, excelling in early termination for unbalanced trees but potentially using more memory.

Key Insights

• Min Depth: Shortest root-to-leaf path.
• DFS: Explores all paths recursively.
• BFS: Finds shortest path level-wise.

Additional Example

For root = [1,2,3,4,null,null,5]:

• Goal: 2.
• DFS: Min depth via 1->2 = 2.

Edge Cases

• Empty Tree: [] → 0.
• Single Node: [1] → 1.
• Unbalanced: [1,2,null,3] → 2.

Both solutions handle these well.

Final Thoughts

LeetCode 111: Minimum Depth of Binary Tree in Python is a fundamental depth challenge. The Recursive DFS solution stands out for its efficiency and clarity, while Queue-Based BFS offers a level-wise alternative. Want more? Try LeetCode 104: Maximum Depth of Binary Tree for max depth or LeetCode 94: Binary Tree Inorder Traversal for traversal basics. Ready to practice? Solve LeetCode 111 on LeetCode with [3,9,20,null,null,15,7], aiming for 2—test your skills now!