Python3 Recursive and Iterative Solution (one stack) With Detailed Explanations.
Please upvote this because I think my iterative solution is much better than what I saw in the top comments.\n\nRecursive solution: \nThis is basically the same
Please upvote this because I think my iterative solution is much better than what I saw in the top comments.\n\n**Recursive solution:** \nThis is basically the same as the other 200 answers so I won\'t comment much about it:\n\n```\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        return self.sortedArrayToBSTHelper(nums, 0, len(nums) - 1)\n    def sortedArrayToBSTHelper(self, nums, floor, ceiling):\n        if floor > ceiling: return None\n        middleIndex = (floor + ceiling) // 2\n        n = TreeNode(nums[middleIndex])\n        n.left = self.sortedArrayToBSTHelper(nums, floor, middleIndex - 1)\n        n.right = self.sortedArrayToBSTHelper(nums, middleIndex + 1, ceiling)\n        return n\n```\n\n**Iterative Solution:**\n\n```\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        if not nums: return None\n        \n        # Each item in the stack holds: floor, ceiling, parent and parent\'s direction.\n        stack = [(0, len(nums) - 1, None, None)]\n        root = None\n        while stack:\n            floor, ceiling, parent, direction = stack.pop()\n            middleIndex = (floor + ceiling) // 2\n            n = TreeNode(nums[middleIndex])\n            \n            # Add the root node. parent should only ever be null in this one case.\n            if not parent:\n                root = n\n            else:\n                if direction == \'l\':\n                    parent.left = n\n                elif direction == \'r\':\n                    parent.right = n\n            \n            # Add the next items to the stack, as necessary. Add right first.\n\t\t\t# Similar to the recursive approach, both floor and ceiling should never cross.\n            if middleIndex + 1 <= ceiling:\n                stack.append((middleIndex + 1, ceiling, n, \'r\'))\n            if floor <= middleIndex - 1:\n                stack.append((floor, middleIndex - 1, n, \'l\'))\n        return root\n```\n\nHere\'s how I approached this.\n\nFirst, let\'s talk about the stack. Each item in the stack is to hold four items.\na) b) The floor and ceiling: exact same functionaliy to the recursive approach above. They\'re used as array indices to get the middle value.\nc) The parent node\nd) The \'direction\'. Two options here: either \'l\' to indicate left or \'r\' to mean right. These are just arbitrary letters I chose.\n\nSo the first item in the stack is the root node. The floor and ceiling will be the first and last index in the list respectively, and its parent and direction are None since the root can\'t have a parent.\n\nNow let\'s talk about the loop.\n\n1) I pop the item at the top of the stack. Using the floor and ceiling indices, I get the middleIndex and make a new node of nums[middleIndex]. \n2) If the item I just popped doesn\'t have a parent, that means this is a root. This should only ever happen once and that\'s at the very beginning when the loop pops the first item out. For all other cases, it have a parent.\n3) If a parent exists, then a direction should be provided. The direction basically says, \'Ok so I just made a new node n from 1) above and I have a reference to a parent node. Is n the left or right child of the parent node\'? If the direction is \'l\' it\'s the left, otherwise it\'s the right.\n4) Now, we need to add items to the stack. We have two if statements here that check if a left or right child is even possible. If so, add to the stack a new item with the appropriate indices for floor and ceiling, the parent will be the node we made from 1) so n, and the direction will be either \'l\' or \'r\' depending on the indices provided for the floor and ceiling. Please note that I added right first then left. I did that on purpose because this is a stack, so by adding right then left, the left is what will be at the top. Really it doesn\'t matter here for this question, but the goal is to mimick DFS pre-order traversal, and that means current, left then right.\n\nI hope this helps.\n\nIf you have questions about the code, comment or dm me. If you have questions about life, idk.\n\n
['Recursion', 'Iterator', 'Python3']