Why is the space complexity of a recursive inorder traversal O(h) and not O(n)
<p>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.</p>

<p>Why is that? Lets say that this is the code for the traversal:</p>

<pre><code>public void inorderPrint (TreeNode root) {

    if (root == null) {
        return;
    }

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

}
</code></pre>

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

<p>What am I missing? </p>