Understanding references in Java; addNode() function for BST is not behaving as it should

Question

I'm trying to understand why my first implementation of addToTree() doesn't work, but the second one does. I have commented the lines that are different:

public static void addToTree(Node n, int value){ //return type is void
    if (n != null){
        if (n.val >= value){
            addToTree(n.left, value);
        } else { 
            addToTree(n.right, value);
        }
    } else {
        n = new Node(value);
    }
}

Here is the implementation that actually works:

public static Node addToTree(Node n, int value){ //return type is Node
    if (n != null){
        if (n.val >= value){
            n.left = addToTree(n.left, value); //sets n.left with the return value
        } else { 
            n.right = addToTree(n.right, value); //sets n.right with the return value
        }
    } else {
        n = new Node(value);
        return n; //returns the new node after creating (adding) it
    }
    return n;
}

Why do I have to set n.right and n.left to the return value from addToTree()? I don't understand why a void function wouldn't work here and why the new node has to be returned. Does this explain the 'Pass by value' nature of Java? When addToTree(n.left, value) is called, is it not passing the reference to n.left?

Answer 1

Short answer: Java is pass-by-value, and NOT pass-by-reference

Long answer: Since Java is pass-by-value, any values when passed in a method will first be copied first to a different location in memory, and that location is passed to the method. And when the method changes the value, the value at the new (i.e. copied) location will change, leaving the original copy as it is.

In case of primitive values, only the value is copied to new location, but in case of reference-type values when passed to a method will also get copied, but since they are reference to some other location, the location that reference is pointing to will still be the same.

Here in your case, when you passed n.left/right in next recursive call, the reference is copied to a different location, and last call of recursion wrote n=new Node(value); in that different location, but actual node.left/right was left unchanged.

I know all this is confusing when you see reference-type being passed as pass-by-value. Understanding why passing two ints to a method to swap doesn't work, but passing an array of two elements, and swapping values in the array work in Java. The concept basically is the same. Check this link for more info: Java: Why does this swap method not work?