CODEWITHSUNDEEP
java
Darlyn
Darlyn

Reputation: 4938

Reference in java

I am learning java. 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 remain null . The recursion does not return the reference to the newly created Node so the value isn't 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!

Upvotes: 0

Views: 82

Answers (1)

jonhopkins
jonhopkins

Reputation: 3842

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.

Upvotes: 2

Related Questions