111

111. Minimum Depth of Binary Tree

No point in using depht-first search for this question, we’re going to end up wasting time traveling paths that aren’t the minimum. The optimal solution would be to use breadth-first search, allowing us to travel through the binary tree level by level, enabling us to visit less nodes.

We maintain a queue of nodes to explore, starting with root. We grab the length of the queue at the current level and dequeue nodes until we’ve processed all nodes at the current level. If we find a leaf node, a node with None for its left and right children, we know we’ve reached the minimum depth. Why? Because we’re using breadth-first search, the first leaf node we encounter will always be at the minimum level.

The solution is as follows:

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

_ Time Complexity:

O(n) - We inspect all nodes in the binary tree.

_ Space Complexity:

O(n) - We maintain a stack of nodes to explore.