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