# Iterative solution in python

• In case anyone was wondering what an iterative solution looks like in python, here is one. Around 100ms, so apparently not any faster than a recursive solution - probably due to the extra if's needed to make it work. No pointers or references make this somewhat tricky and less efficient than it could be with them.

class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if not nums:
return None
lb=0
ub=len(nums)
middle = ub>>1
root = TreeNode(nums[middle])
walker = root
if ub - middle > 1:
rights = [(root,middle+1,ub)]
else:
rights = []
ub=middle
while 1:
diff = ub-lb
if diff:
middle = lb+(diff>>1)
walker.left = TreeNode(nums[middle])
walker = walker.left
elif rights:
walker,lb,ub = rights.pop()
diff = ub-lb
middle = lb+(diff>>1)
walker.right = TreeNode(nums[middle])
walker = walker.right
else:
break
if ub - middle > 1:
rights.append((walker,middle+1,ub))
ub=middle

return root

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