Fast pyhon iterative and recursive solutions (56ms)

• Most people use recursive solutions. I'm sharing my iterative solutions, which would be faster since it doesn't have to go through the entire tree (especially for extremely unbalanced trees). The ideas is based on Binary Tree Level Order Traversal. The best runtimes on OJ is 56ms.

Solution 1-4 are based on similar ideas. Solution 4 is longer but easier to understand and should be the fastest.

(I did some test, for big balanced trees, iterative Solution 3 and 4 are the fastest, faster than 1,2, and recursive solutions)

Solution 1, iterative, shortest, 6 lines

``````def minDepth(self, root):
depth, level = 0, [root]
while level and level[0]:
depth += 1
NotLast = (None,None) not in [(n.left, n.right) for n in level ]
level = NotLast and [k for n in level for k in (n.left,n.right) if k]
return depth
``````

(note: if `NotLast`=False, it would turn `level` into `False` and then leave the while loop)

Solution 2, iterative, 8 lines

``````def minDepth(self, root):
depth, level = 0, [root]
while level and level[0]:
depth += 1
for n in level:
if not n.left and not n.right:
return depth
level = [kid for n in level for kid in (n.left,n.right) if kid]
return depth
``````

Solution 3, iterative, 10 lines

``````def minDepth(self, root):
depth, level = 0, [root]
while level and level[0]:
depth += 1
temp = []
for n in level:
if not n.left and not n.right:
return depth
temp.extend([kid for kid in (n.left, n.right) if kid])
level = temp
return depth
``````

Soltion 4, iterative, 14 lines. (An expansion of 1-3, easier to understand)

``````def minDepth(self, root):
depth, level = 0, [root]
while level and level[0]:
depth += 1
temp = []
for n in level:
l, r = n.left, n.right
if not l and not r:
return depth
if l:
temp.append(l)
if r:
temp.append(r)
level = temp
return depth
``````

Solution 5, recursive, 5 lines

``````def minDepth(self, root):
if not root:
return 0
if not root.left or not root.right:
return 1+max(self.minDepth(root.left),self.minDepth(root.right))
return 1+min(self.minDepth(root.left),self.minDepth(root.right))``````