trolkura - 1 year ago 43

Java Question

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 Source

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.