```
class Solution:
# @param root, a tree node
# @return an integer
def minDepth(self, root):
if not root:
return 0
explored = [(root, 1)]
while explored:
(node, depth) = explored.pop(0)
if node.left is node.right is None:
return depth
if node.left:
explored.append((node.left, depth+1))
if node.right:
explored.append((node.right, depth+1))
```

I store explored nodes with their depth. Notice that I add new nodes to the end (`.append()`

) while I take them from the head (`.pop(0)`

) -- in this way I am sure to always find the shortest depth nodes first.