Iterative and Recursive Python Solutions with Detailed Explanations
Summary\nWe know that the input list is sorted.  At a high level, we know the root of our binary search tree will be the center value in that sorted list, so th
### Summary\nWe know that the input list is sorted.  At a high level, we know the root of our binary search tree will be the center value in that sorted list, so the left and right subtrees will have the same number of nodes (within 1 node).  Then, we somehow want the left branch to be properly composed with the values to the left of the center value, and the right branch properly composed with values to the right of the center value; this ensures that we have a root, and the left and right branches will be evenly sized from the sorted property.\n\n### Recursive\nThe recursive solution to this problem is essentially direct translation of the aforementioned "definition" of the root and the left and right branches.  The base case would be no values in nums, so the function implicitly returns None.  With 2-3 nodes, the root is set, then the left and right children would be either a node or None (the result of the recursive call with one or zero values in nums).  Then, the recursive call on a non-None child would then have no more values in nums, because the children of the original root used up the remaining values in the original nums, so their children would be None.\n\n```\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        # continue while this branch has values to process\n        if len(nums) > 0:\n            # create node from center point of nums\n            i = len(nums) // 2\n            root = TreeNode(nums[i])\n            \n            # the left node becomes the recursive sorted BST of the items\n            # to the left of the center point, and the right node becomes\n            # the recursive sorted BST of the items to right of center point\n            root.left = self.sortedArrayToBST(nums[:i])\n            root.right = self.sortedArrayToBST(nums[i+1:])\n            \n            # return the root, whose children will be properly set\n            return root\n        \n        # notice that Python functions implicitly return None, so children\n        # that call sortedArrayToBST recursively but with no values remaining\n        # will be set to None, as desired\n\'\'\'\'\'\'\n```\n\n### Iterative\nThe recursive solution is very natural.  To reformat it as iterative, the overall idea is to create a stack that keeps track of tuples of information of child nodes we need to create, and each tuple keeps track of the childs parent and the side of the parent that the child will become.  Because we only push child tuples to the stack after their parents are created, the process will create the children until we reach the base case, whereby that branch has exhausted its corresponding chunk of the original nums.\n\n```\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        # ensure we have at least the root\n        if not nums: return None\n        \n        # we will be creating a stack where each element is the following tuple:\n        # (left index of nums, right index of nums, parent node, child side),\n        # where the left and right indices set the bounds of the values in\n        # nums the current node considers, and child side refers to which side\n        # of the parent node that the current node will be set to (more clear below)\n        \n        # create the root, which is the "first parent"\n        l, r = 0, len(nums) - 1  # initial left and right bounds of nums\n        i = (l + r) // 2         # center of the bounds of nums we view\n        root = TreeNode(nums[i]) \n        \n        # create a stack of the first two children values; split bounds of\n        # parent\'s left and right bounds in half using the center position,\n        # then remember the side of the parent (root) to set that child to\n        stack = [(l, i-1, root, \'l\'),\n                 (i+1, r, root, \'r\')]\n        \n        # while there are more children to create\n        while stack:\n            # extract the information for a child\n            l, r, parent, side = stack.pop()\n            \n            # only create the child if it looks at a valid left and right bound\n            # in nums, so the left index <= right index; this ensures we stop\n            # adding children after we\'ve exhausted the valid positions in nums\n            if l <= r:\n                i = (l + r) // 2 # center position of bounds\n                \n                # create the child node from the center position,\n                # and set the corresponding child side in the parent\n                child = TreeNode(nums[i])\n                if side == \'l\': parent.left = child\n                else:           parent.right = child\n                    \n                # add the information for the two children of the current child,\n                # splitting the left and right bounds of the current child in half\n                # using the center position, then remember the side of the child\n                # (which becomes the parent for its children) to set next children\n                stack.append((l, i - 1, child, \'l\'))\n                stack.append((i + 1, r, child, \'r\'))\n        \n        return root\n```\n\nThe iterative solution is a bit more convoluted than the natural recursive solution, but I think it\'s a great exercise to write your solutions both iteratively and recursively.
[]