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?

You are not just pushing -- you are popping. Thus, certain parts of the stack are used more than once. The height of the tree controls how much you push before you can pop. By the way -- I think that you have a typo, shouldn't the function be calling itself rather than `preorderPrint`? — John Coleman, Dec 17 '16 at 18:50
See this for clearer answers : https://stackoverflow.com/questions/33590205/how-do-you-find-the-space-complexity-of-recursive-functions-such-as-this-one — Abhijeet Khangarot, Nov 19 '19 at 07:25

score 31 · Accepted Answer · answered Dec 17 '16 at 21:51

31

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.

answered Dec 17 '16 at 21:51

Stefan Haustein

18,427
3
36
51

RBT · Answer 2 · 2022-01-25T12:54:00.687

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:

Number of nodes, n = 3

Number of stack frames required in recursive traversal = 3

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.

It definitely depends on the characteristics of your binary tree. For the general case, yes, worst case will be `O(N)` for an unbalanced tree. But if you know for a fact that your tree is balanced (e.g. AVL or red black), then you are guaranteed that the height of your tree will be at most `Log(N)`, and so your space complexity will be `O(log N)` for the traversal as well. — Eric Cornelson, Nov 17 '18 at 21:29

score 1 · Answer 3 · answered Nov 19 '19 at 07:24

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).

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

3 Answers3