< Back





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.