recursion method in binary search tree-java

Question

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;
}

The code itself looks fine Lori. It is possible that your tree has orphaned nodes after the first insert, causing future inserts to return true. — Krish Srinivasan
– Krish Srinivasan, Commented Oct 30, 2014 at 14:19
@algorithmic the code is wrong. Assume the tree contains 3 6 9 7 with root 3. When you try to insert a 6 the second if case is matched. The recursive call of insert will set the right descendant of 3 to some value. But returned will be the node with value 3. — user
– user, Commented Oct 30, 2014 at 15:38
@User - on the first call to insert(value,travel), the second case is matched. in that case insert(value, travel.right) is called and now null is returned. that is what travel.right will be set to when coming out of the recursion. and return travel will return null. So it does work ok, in the the first insert case. However the insert code is not actually shown. so, it is unclear what changed with the second insert case - that is when insert(9) is called. — Krish Srinivasan
– Krish Srinivasan, Commented Oct 30, 2014 at 17:02
@algorithmic travel cant be null. If it was null the first case would match what do you mean that the insert code is not shown?! Its a recursive call so everything is shown. — user
– user, Commented Oct 30, 2014 at 17:08
@user - the actual insertion into the tree is not shown. if this is the only code and the tree is preconstructed, the code has no issues. what do you mean travel cant be null? if the value is neither greater nor smaller, then the last return is reached "return null". — Krish Srinivasan
– Krish Srinivasan, Commented Oct 30, 2014 at 17:33

user · Accepted Answer · 2014-10-30 13:34:47Z

1

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.

answered Oct 30, 2014 at 13:34

user

7451 gold badge7 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Parth Satra · Accepted Answer · 2014-10-30 13:38:37Z

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);
    }
}

Collectives™ on Stack Overflow

recursion method in binary search tree-java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related