Two similar algorithms for inserting into a Binary Search Tree

Question

I asked a similar question last time around concerning the second algorithm below and was referred to a Is Java “pass-by-reference” or “pass-by-value”? thread.

I get that when you pass a variable into a method, Java creates a shadow copy of it so you can't modify the original variable, but this is exactly what is confusing me.

Below are two somewhat similar algorithms to which I initially pass in a root Node-- the first one works but the second one doesn't.

First

public void insert(int element) {
    Node temp = new Node(element);

    if(root == null) {
        root = temp;
        root.parent = null;
        size++;
    } else {
        insert(root, temp); 
        size++;
    }
}

private void insert(Node current, Node temp) {
    if(temp.element < current.element) {
        if(current.leftChild == null) {
            current.leftChild = temp;
        } else {
            insert(current.leftChild, temp);
        }
    } 
    else if(temp.element >= current.element) {
        if(current.rightChild == null) {
            current.rightChild = temp;
        } else {
            insert(current.rightChild, temp);
        }
    }
}

Ouput:

Second (doesn't work)

public void insert(int data) {
    Node temp = new Node(data);

    if(root == null) {
        root = temp;
        size++;
    } else {
        insert(root, temp);
        size++;
    }
}

private void insert(Node current, Node temp) {
    if(current == null)
        current = temp;
    else if(temp.element < current.element)
        insert(current.leftChild, temp);
    else if(temp.element >= current.element)
        insert(current.rightChild, temp);
}

Output:

I wrote the first one myself and got the second one from Wikipedia. Why does the first one work but not the second one?

Answer 1

let's look at what references are. (Java-references, not to be confused with C++-references)

Let's assume we have some memory with addresses, in this case the data is some String Object

[ address ][ data ]
[       0 ][  abc ]
[       1 ][   de ]
[       2 ][    y ]
[       3 ][  foo ]
[       4 ][ baar ]

If we have a reference, than this reference is only an address, not the data itself!

int i = 15; // this is a primitive type, the variable i holds the data directly
            // 15 in this case

Number x = new StringObject(foo); // this is a reference, the reference only 
                                  // contains the address.
                                  // so x is actually '3'

Now, what happens if we call a method? Every value passed to a method will be copied.

void call(int x) {
    x = 4;
}

int i = 15;
call(i);
System.out.println(i);

The output of this will be 15. because, the value of i gets copied to the call method. And the method only changes the copy, but not the original i.

The same goes for references:

void call(StringObject x) {
    x = new StringObject("baz"); // this creates a new address in x!
}

StringObject i = new StringObject("foo"); // remember, i is only an address!
                                          // the address is '3'
                                          // the actual value can be looked up
                                          // in our memory table above
                                          // '3' -> 'foo'

call(i);
System.out.println(i);

The output here will be foo. As with the primitives, i will be copied. But don't worry, only the address will be copied. The result is, that the call method works on a copy of i which is 3. But the value of the original i is not changed.

So, what is the connection to your problem? See this method:

private void insert(Node current, Node temp) {
    if(current == null)
        current = temp;
    else if(temp.element < current.element)
        insert(current.leftChild, temp);
    else if(temp.element >= current.element)
        insert(current.rightChild, temp);
}

Clearly as you can see, your code operates on the copy of the current reference! You are changing a copy which will be discarded after the method. Basically the solution to your problem with the second code is to use the first code snippet. You could work with some wrapper object, like C++-references, but this get's complicated and will be error prone.

Answer 2

It does not work because you do not connect the element 'temp' in the tree. Suppose you reached the point where you have to add temp in the tree. Suppose at some stage you have current and

current.leftchild=null and you have to add temp here.What is done in second method is you got to current.leftchild and assign temp to it , but you have not actually pointed the left pointer to temp.Thus temp will be inaccessible and no tree is formed. That is you have to keep return type Node to solve the problem.