# Python ITERATIVE solution

• Sometimes interviewers ask us about iterative version of recursive algorithm, so here we go.

``````def is_done(node, depths):
left, right = node.left, node.right
return (not left or left in depths) and (not right or right in depths)

class Solution(object):
def isBalanced(self, root):
stack, depths = [root], {}
while stack:
node = stack.pop()
if not node: continue
if is_done(node, depths):
left  = 0 if not node.left  else depths[node.left]
right = 0 if not node.right else depths[node.right]
if abs(left - right) > 1: return False
depths[node] = 1 + max(left, right)
else:
if node.left and node.left not in depths:
stack += node, node.left
else:
stack += node, node.right
return True
``````

• Just a quick hack:

``````def isBalanced(self, root):
nodes = [root]
for node in nodes:
if node:
nodes += node.left, node.right
depth = {None: 0}
for node in reversed(nodes):
if node:
left, right = depth[node.left], depth[node.right]
if abs(left - right) > 1:
return False
depth[node] = 1 + max(left, right)
return True``````

• @StefanPochmann haha that's fun. I came up with another one.

``````class Solution(object):
def isBalanced(self, root):
stack, node, last, depths = [], root, None, {}
while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack[-1]
if not node.right or last == node.right:
node = stack.pop()
left, right  = depths.get(node.left, 0), depths.get(node.right, 0)
if abs(left - right) > 1: return False
depths[node] = 1 + max(left, right)
last = node
node = None
else:
node = node.right
return True

``````

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