0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ good catch, my bad $\endgroup$ – dadrake Dec 20 '18 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.