Convert Sorted Array to Binary Search Tree with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nThe idea here is to recursively split the input array in half and use the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nThe idea here is to recursively split the input array in half and use the middle element as the root of the current subtree. We do this until there are no more elements left in the array, in which case we return None. We then build up the tree by recursively calling the function on the left and right halves of the array and setting the resulting trees as the left and right children of the current root node. Finally, we return the root node of the completed tree.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:\n        if not nums:\n            return None\n        mid = len(nums) // 2\n        root = TreeNode(nums[mid])\n        root.left = self.sortedArrayToBST(nums[:mid])\n        root.right = self.sortedArrayToBST(nums[mid+1:])\n        return root\n\n```
['Array', 'Divide and Conquer', 'Tree', 'Python', 'Python3']