# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param {TreeNode} root
# @return {integer}
def minDepth(self, root):
if not root:
return 0
nodes = collections.deque([(root, 1)])
while nodes:
node, curDepth = nodes.popleft()
if node.left is None and node.right is None:
return curDepth
if node.left:
nodes.append((node.left, curDepth + 1))
if node.right:
nodes.append((node.right, curDepth + 1))
Simple Python recursive solution (BFS)  O(n) 80ms


(Edit: This was about the old version using list instead of deque.)
This is not O(n) but O(n^2), since every
nodes.pop(0)
takes linear time. If you have a complete tree, then popping the root shifts zero nodes, popping the next shifts one node, popping the next shifts two nodes, then three, then four, etc. You have a a quadratic amount of shifts.