Will objects on heap be replicated on stack on function call?

Question

In Java, would an on-heap object be replicated on stack when a method is called? Consider this code -

static void mirror(Node p){
    if (p!=null) {
        Node temp = null;
        temp = p.left;
        p.left = p.right;
        p.right = temp;

        mirror(p.left);
        mirror(p.right);
    }
}

Would the space complexity be -

1. O(n) because the Node object p is pushed/replicated on stack on every recursive call
2. O(1) because the Node object is already in memory and p is just a reference to it
3. O(n) because the reference p is being pushed on stack on method calls

Edit: where n is the depth of the tree

Answer 1

Neither of them.

Objects are not copied when passing their references to parameters of a method invocation, but references itself still occupy stack space, so the space-complexity is O(n) assuming that n refers to the depth of your binary tree.

The O(…) notation ignores constant scale factors, therefore O(n) only implies that there is an amount of stack space required for every recursion which is even true if you don’t pass any parameter to the invoked method. It does not tell how much space is required.

---

Edit: now that you have edited your question adding point 3, it’s point 3, but not exactly because, as said, there is stack space required even if you don’t push a reference on the stack.

---

Also keep in mind that you have to make clear what n refers to. If n is the total number of Nodes of your tree, it’s rather O(log(n)) if the tree is balanced. But if n is the maximum depth of your tree which matches the maximal recursion depth, then it’s O(n).