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

Question

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?

• greybeard: "performing a worst case binary search" There is no search involved. Binary search can be done in constant additional space.

Answer 1

I would say try to think about it more in the terms of data structures used directly in the calculation of the result. Typically you wouldn't consider the call stack because you could in theory rewrite you algorithm to be iterative and have no issues with the call stack. The call stack is only an issue when you reach the max recersion depth. It is also not considered when just analyzing algorithms.

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.

• greybeard: Please argue how to Create a [linked] binary search tree from a sorted array in better than O(n) time for $n$ nodes.

Answer 2

Besides the recursive calls, the function recursive_insert does not require local variables, hence no extra space.

The arguments are nums, left, right, and two situations could arise:

• the whole of nums is copied on every call, causing $n$ elements to be stored on the stack, for a total of $n\log n$ extra space.

• only a reference to nums is used, and the extra space is just proportional to $\log n$.

Note that, assuming that the copies cannot be avoided, the list need not be copied in full every time. On the opposite, every recursion level can do with the half of the previous and the total stack space requirement will be $\frac n2+\frac n4+\frac n8\sim n$.