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?
performing a worst case binary search
There is no search involved. $\endgroup$