Minimum Depth of Binary Tree Interview Question for Google

## Minimum Depth of Binary Tree

This problem asks us to find the minimum depth of a binary tree, which is the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf node is a node with no children.

### Naive Solution: Depth-First Search (DFS)

The most straightforward approach is to use Depth-First Search (DFS) to traverse the tree and keep track of the depth of each node. When we reach a leaf node, we update the minimum depth if the current depth is smaller than the current minimum depth.

```python
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: TreeNode) -> int:
        if not root:
            return 0
        
        min_depth = float('inf')
        
        def dfs(node, depth):
            nonlocal min_depth
            
            if not node.left and not node.right:
                min_depth = min(min_depth, depth)
                return
            
            if node.left:
                dfs(node.left, depth + 1)
            if node.right:
                dfs(node.right, depth + 1)
        
        dfs(root, 1)
        return min_depth

Optimal Solution: Breadth-First Search (BFS)

Breadth-First Search (BFS) can also be used to solve this problem. BFS explores the tree level by level. The first leaf node we encounter will be at the minimum depth. This approach can be more efficient than DFS because it stops as soon as it finds the first leaf node.

from collections import deque

class Solution:
    def minDepth(self, 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 # Should not reach here if the tree is valid

Big(O) Run-time Analysis

DFS: In the worst case, we may need to visit all nodes in the tree. Therefore, the time complexity is O(N), where N is the number of nodes in the tree.
BFS: Similar to DFS, in the worst case, we may need to visit all nodes. Therefore, the time complexity is O(N), where N is the number of nodes in the tree. However, in practice, BFS may be faster because it stops as soon as the first leaf node is found.

Big(O) Space Usage Analysis

DFS: In the worst case (skewed tree), the recursion stack may contain all nodes in the tree. Therefore, the space complexity is O(N), where N is the number of nodes in the tree. In the average case (balanced tree), the space complexity is O(log N), where N is the number of nodes in the tree.
BFS: In the worst case (complete binary tree), the queue may contain all nodes at the lowest level of the tree, which is approximately N/2 nodes. Therefore, the space complexity is O(N), where N is the number of nodes in the tree.

Edge Cases

Empty Tree: If the root is None, the minimum depth is 0.
Root with Only One Child: The minimum depth is the depth of the path to the nearest leaf node. We must ensure we are actually at a leaf node and not just a node with a single child. For example, consider [1,2]. The minimum depth is 2, not 1.
Large Tree: The algorithm should be able to handle a tree with a large number of nodes without running into stack overflow issues (DFS) or memory issues (BFS).

Here's how the given examples are handled:

Example 1: root = [3,9,20,null,null,15,7] The BFS algorithm will find the leaf nodes 15 and 7 at depth 3, but it encounters the leaf nodes 9 first at depth 2, so the minimum depth is 2.
Example 2: root = [2,null,3,null,4,null,5,null,6] The BFS algorithm will traverse through the tree, with only right children, and eventually find the leaf node 6 at depth 5. So the minimum depth is 5.