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.