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:

enter image description here

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:

enter image description here

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

No. If I insert numbers from [1-9], the first algorithm will allow my tree to print out all the numbers, while the second one only stores "1" — Haque1, May 22 '14 at 10:54
Your code doesn't match the C++ version in Wikipedia. You can't pass a reference to a pointer in Java, nor do you create a new Node as it does in the original code. — Peter Lawrey, May 22 '14 at 10:55
@migdal Logic error: _someNode.rightChild = temp;_ appears nowhere in the second. — schmop, May 22 '14 at 10:55
what is confusing you ? Object is pass by reference and primitive type is pass be value. — Macrosoft-Dev, May 22 '14 at 10:55
@Macrosoft-Dev All arguments are passed by value, even references are passed by value. — Peter Lawrey, May 22 '14 at 10:56

advocateofnone · Answer 1 · 2014-05-22T11:07:57.053

1

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.

edited May 22 '14 at 11:07

answered May 22 '14 at 10:58

advocateofnone

2,527
3
17
39

no when you return you have to catch the element also somewhere !! – advocateofnone May 22 '14 at 11:42

Absurd-Mind · Accepted Answer · 2014-05-22T11:36:29.777

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.

Two similar algorithms for inserting into a Binary Search Tree

2 Answers2