Why is the space complexity of a recursive inorder traversal O(h) and not O(n)

Question

So I know that the space complexity of a recursive in order traversal is O(h) and not O(n) as h = tree height and n = number of nodes in the tree.

Why is that? Lets say that this is the code for the traversal:

public void inorderPrint (TreeNode root) {

    if (root == null) {
        return;
    }

    inorderPrint(root.left);
    System.out.println(root.data);
    inorderPrint(root.right);

}

We are pushing n memory addresses to the call stack, therefore, the space complexity should be O(n).

What am I missing?

Answer 1

The addresses are removed from the stack when returning. This space is re-used when making a new call from a level closer to the root. So the maximum numbers of memory addresses on the stack at the same time is the tree height.

Answer 2

IMHO, you should treat the space complexity as O(n) instead. While dealing with space and time complexities in Big O notation we always try to give the complexity value as a function of number of input elements which is n in this case.

Also, if you consider the cases of right skewed binary tree or a left skewed binary then you would find this O(n) space complexity as a fitting one. Have a look at below cases of right skewed binary tree:

  1
 / \
    2
   / \
      3

Number of nodes, n = 3

Number of stack frames required in recursive traversal = 3

  1
 / \
    2
   / \
      3
     / \
        4
       / \

Number of nodes, n = 4

Number of stack frames required in recursive traversal = 4

So you can conclude that O(n) is a fitting space complexity in such a worst case scenario (w.r.t. tree structure). In all other cases/types of trees number of stack frames required would always be less than n. And that is how we express complexities. The actual space taken by all possible cases should always be less than or equal to the depicted function.

Also, in all cases always it will be O(h) <= O(n). So thinking the space complexity as O(n) just gives us a uniform way of thinking in terms of input number of elements. Although, O(h) space complexity is equally correct due to the reasons mentioned by @StefanHaustein in his answer.

Answer 3

Space complexity of recursion is always the height / depth of recursion, so following this general rule, there can be at most h height in inorder traversal, where h is the length of deepest node from root. Space complexity of recursion = O(depth of recursion tree).