# Create a binary search tree from a sorted array: Space complexity reasoning

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?

Space complexity is constant or $$O(1)$$ because you can modify the tree in place.
Your answer about call stacks more so relates to the worst-case time complexity as this is directly related to number of function calls (or call stacks in your case). This is going to be $$O(\text{height})$$ of the tree which is at most $$n$$, so $$O(n)$$ in worst case, but $$\Theta(\log(n))$$ in average case. The time complexity can be improved to better than $$O(n)$$ if you keep your tree balanced after each insertion.