# Simple Python recursive solution (BFS) - O(n) 80ms

• ``````# 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))``````

• (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.

• Good catch. For future reference, one can simply change the `[]` to `collections.deque()` to get the real `O(n)` run time. (use double linked list array instead of a normal array)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.