[Python3] Two Solutions Explained with Diagrams
0. Understanding the Problem\nWe are given a sorted array, with elements in ascending order.\n\nThe goal is to create a height balanced binary search tree. This
## 0. Understanding the Problem\nWe are given a sorted array, with elements in ascending order.\n\nThe goal is to create a height balanced binary search tree. This tree follows the following properties:\n- The right sub-tree itself is height balanced BST.\n- The left sub-tree is also height balanced BST.\n- The heights of right and left trees only differ by 1 **atmost**.\n\n![height balanced BST](https://i.imgur.com/yL7hlko.png)\n\n*To find if right sub-tree is balanced, we assume the `root.right` node is `root` and check its own sub-trees. We do this recursively. Similarly for the left node to the root.*\n\nLet\'s look at a couple of examples to find some patterns.\n\n## 1. Examples\n![examples](https://i.imgur.com/gx9dJBY.png)\n\n**Observation: The middle element is always the root. In case there are two middle elements, either can be the root.**\n\n![more complicated example](https://i.imgur.com/y6UHwNx.png)\n\n**Observation: After we find the middle element, we can split the tree into two parts, and then solve the problem recursively, for each of the sub-tree.**\n\n*Note that this approach works because we always keep the constraint of height-balanced tree in place!*\n\n## 2. Code (inefficient)\n```\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        # base case\n        if not nums: return None\n        \n        # getting the mid\n        mid = len(nums)//2\n        node = TreeNode(nums[mid])\n        \n        # left node is given the responsibility till mid, \n        # but not including mid\n        node.left = self.sortedArrayToBST(nums[:mid])\n        # right node is given the responsibility from mid+1 \n        # till the end\n        node.right = self.sortedArrayToBST(nums[mid+1:])\n        return node\n```\n\nThe space and time complexities are `O(N)` both. However, the above can be made a bit more efficient - by not passing copies of `nums[:mid]` or `nums[mid+1:]`. Instead, we can pass the indices. This will reduce the space complexity.\n\n## 3. Code (efficient)\n```\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        def recurse(l, r):\n            # base case, l must always be <= r\n            # l == r is the case of a leaf node.\n            if l > r: return None\n            mid = (l+r)//2\n            node = TreeNode(nums[mid])\n            node.left = recurse(l, mid-1)\n            node.right = recurse(mid+1, r)\n            return node\n        # both the indices are inclusive,\n        # mathematically given by: [0, len(nums)-1]\n        return recurse(0, len(nums)-1)\n```\n\nIn this case the time complexity is the same, `O(N)`, but the space complexity is now `O(log(N))`. We just need to consider the maximum height of the stack while recursion. This is `log(N)` becasue we are dealing with height-balanced BST!\n
['Recursion', 'Python', 'Python3']