[Python] short recursion solution, explained
This problem is the simple version of problem 109. Convert Sorted List to Binary Search Tree: here what is given not sorted linked list, but sorted array, so we
This problem is the simple version of problem **109**. Convert Sorted List to Binary Search Tree: here what is given not sorted linked list, but sorted array, so we can have access to any element of this array in `O(1)`. So, the idea is straightforward: just divide our array into two almost equal halves on each iteration and attach recursive run for the left part as left subtree and recursive run for the right part as right subtree.\n\n#### Complexity\nTime complexity is `O(n)` time and `O(log n)` memory because of implicit stack of recursion.\n\n#### Code\n```python\nclass Solution:\n    def sortedArrayToBST(self, nums):\n        def helper(beg, end):\n            if beg > end: return None\n            mid = (beg + end)//2\n            root = TreeNode(nums[mid])\n            root.left = helper(beg, mid - 1)\n            root.right = helper(mid + 1, end)\n            return root\n        \n        return helper(0, len(nums) - 1)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Recursion']