CODEWITHSUNDEEP
javarecursionbinary-search-tree
user4147700
user4147700

Reputation:

recursion method in binary search tree-java

I am trying to write a boolean recursive method that inserts values into a binary search tree. It returns true if the value is not already there and inserts it and returns false if there already is that same value there and the list does not get changed. I think this works for the most part, but it fails to return false repetitively when multiple values are already there. For example, if the tree already contains 3 9 6 7 and I try to insert 3, it returns false as it is the first time. But then when I try to insert 9 6 or 7, it always returns true, which it should not as those values are already there. 

public boolean insert(int value) {
    Node travel;
    travel=insert(value,root);
    if (travel==null)
        return false;
    root=travel;
    return true;
}

private Node insert(int value, Node travel) {
    if (travel==null) {
        travel=new Node(value);
        return travel;  
    }
    if (value>travel.data) {
        travel.right=(insert(value,travel.right));
        return travel;
    }
    if(value<travel.data) {
        travel.left=(insert(value,travel.left));
        return travel;
    }
    return null;
}

Upvotes: 0

Views: 967

Answers (2)

Parth Satra
Parth Satra

Reputation: 523

I think it can be something like

Initially call with insert(value, root, null) 

public boolean insert(int value, Node currentNode, Node parentNode) {
    if(currentNode == null) { //Node not present, hence insert
         Node valueNode = new Node(value);
         if(parentNode != null && parentNode.value > value) { //link to the parent node
             parentNode.left = valueNode;
         } else if(parentNode != null && parentNode.value < value){
             parentNode.right = valueNode;
         }
         return true; 
    } else if(currentNode.value = value) { //Node present 
         return false;
    } else if(value > currentNode.value) { //Now check the same in right side of the tree
         return insert(value, currentNode.right, currentNode);
    } else if(value < currentNode.value) { //Now check the left side of the tree
         return insert(value, currentNode.left, currentNode);
    }
}

Upvotes: 0

user
user

Reputation: 745

Change it like this:

private Node insert(int value, Node current) {
    if(current.data == value){
        return current;
    }else if(current.left != null && current.left.data > value){
        return insert(value,current.left);
    }else if(current.right != null && current.right.data < value){
        return insert(value,current.right);
    }else{
        if(current.data > value){
            current.left = new Node(value);
        }else{
            current.right = new Node(value);
        }
        return null;
    }
}

This will insert the a Node with the given value if its not already present and return null. Otherwise a Node will be returned which indicates that the Node was already present.

Upvotes: 1

Related Questions