Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'.
class TreeNode: def __init__(self, x): self.right = None self.left = None self.val = x
Here is the solution:
class Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ left = 0 right = len(nums) - 1 return Solution.recursive_insert(nums, left, right) @staticmethod def recursive_insert(nums, left, right): if left <= right: mid = (left + right)//2 node = TreeNode(nums[mid]) node.left = Solution.recursive_insert(nums, left, mid - 1) node.right = Solution.recursive_insert(nums, mid + 1, right) return node example_insertion = Solution() example_insertion.sortedArrayToBST([1, 2, 3, 4, 5, 6, 7, 8])
I understand proving the time complexity is $O(n)$ by using the following recurrence relation:
$$T(n) = 2T(n/2) + C$$
I have a question about the space complexity... Here is how I rationalize it. Please correct me if I'm wrong.
The code to insert the left and the right child involves simply performing a worst case binary search (until left becomes greater than right, or start becomes greater than end). The function call stack keeps getting re-used, but goes to a maximum of $O(\log n)$ (which happens to be the worst case space complexity of binary search when done recursively and not iteratively).
Is my reasoning correct?