Space complexity of construction of a binary tree from inorder and preorder traversals

Question

This question is about SPACE not time complexity. Moreover, it is not about how to solve the question as I was able to do it. I am trying to figure out the space complexity of the algorithm in my solution. I found the question on Leetcode. Assumptions and question description can be found there.

I understand the time complexity as explained in this StackOverflow post but the post doesn't talk of space complexity.

I have tried explaining it after the end of my code.

# Definition for a binary tree node.
class TreeNode(object):
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

class Solution(object):
  def buildTree(self, preorder, inorder):
    """
    :type preorder: List[int]
    :type inorder: List[int]
    :rtype: TreeNode
    """
    preorder.reverse()
    return self.buildTreeHelper(preorder, inorder)

  def buildTreeHelper(self, preorder, inorder):
    if not preorder or not inorder:
      return None

    rootValue = preorder.pop()
    root = TreeNode(rootValue)

    inorderRootIndex = inorder.index(rootValue)

    root.left = self.buildTreeHelper(preorder, inorder[:inorderRootIndex])
    root.right = self.buildTreeHelper(preorder, inorder[inorderRootIndex+1:])
    return root

Because I am sending slices of the list in the recursive function, I am using more space. If we don’t consider clearing up the space, then we need O(n^2) space for the list slices. We could suppose that we are clearing up this space as we proceed but for each step we pass 2n length arrays [pre & inorder] for all of n steps. What is the space complexity if we consider that we clear up the space?

To add to this, the tree could be a linked list in the worst case and so the space taken up in the call stack because of the recursion would be O(n) as well.

Does it make sense to say that the space complexity is then O(n^3) because of each addition to the call stack or have I double counted creating an extra power?

Answer 1

The worst case space complexity of your code is O(n^2). Your basic analysis seems to have it pretty much right. You need O(n) space for each recursive call (for the slices), and in the worst case, your recursive depth might be n as well.

There's no need to multiply in an extra n term for the fact that you have two lists or for the space taken by the recursive call stack. At most those issues would change it from n^2 to 2*n^2 or n^2 + n, and big-O notation ignores constant multiples and slower-growing terms like those.