0

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?

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
brainoverflow
  • 691
  • 2
  • 9
  • 22

2 Answers2

1

The problem with the first implementation is that the new node you create is assigned to n but then n immediately goes out of scope and the reference to that node is lost.

When you declare the method parameter Node n you are defining a variable n of type Node whose scope is limited to this method. When you call the method and pass an argument like addToTree( myNode, myValue ) the variable n inside the method is assigned myNode, like assigning n = myNode. At the end of your method you assign a new value to n. It's similar to doing something like this:

Node myNode = new Node( 7 );
Node n = myNode; // Now n points to the same object as myNode
...
n = new Node( 10 ); // Now n points to a different object

Would you expect myNode to now have a value of 10 at this point? No, because those two variables point to different objects. In your method the variable n is assigned a new node with value but as soon as your method ends, the scope of n ends and the reference to your new node disappears.

So basically you create a new node and then you lose it immediately. You have to return that new node from your method so that somebody can save it somewhere in the tree. In the other lines that you changed, you are saving that new node in the tree, e.g. n.left = addToTree( n.left, value ). This takes the result of the method call which will be the newly created node and stores it the left side of the node n.

Dave S
  • 614
  • 4
  • 6
0

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?

Binayak
  • 96
  • 2