trolkura trolkura - 2 months ago 7
Java Question

Reference in java

I am learning java so i tried to implement basic binary search to understand difference in reference in java and reference/pointers in c++.

The implementations is as following ( using recursion )

class Node{
public int value;
public Node left;
public Node right;
Node( int v ){
this.value = v;
this.left = null;
this.right = null;
}
}
class binarySearch{
public Node root;
public Node insert( int value , Node r ){
if( r == null ){
return new Node( value );
}
if( r.value < value ){
r.left = insert( value , r.left);
}else{
r.right = insert( value , r.right);
}
return r;
}
public void insertIt( int v){
this.root = insert( v , this.root);
}
binarySearch(){
this.root = null;
}
}


and main

binarySearch b = new binarySearch();
b.insertIt(5 );
b.insertIt(6);
Node p = b.root;
while( p != null ){
System.out.println("Hi :" + p.value);
p = p.right;
}


But the left and right nodes remains null . The recursion does not return the reference to the newly created Node so the value isnt inserted to the left/right nodes of root node.

Why is this happening in java? Is there any special way for recursion and reference or how exactly does the reference works in java?

Thanks for explanations or links and help!

Answer

You swapped your logic. In the insert() function:

if (r.value < value) {
    r.left = insert(value, r.left);
} else {
    r.right = insert(value, r.right);
}

should be:

if (r.value > value) {
// or if (value < r.value) {
    r.left = insert(value, r.left);
} else {
    r.right = insert(value, r.right);
}

As it is now, you're inserting 6 into the left node, so it doesn't show up when you're printing the tree.