CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-tree
death7eater
death7eater

Reputation: 1134

Binary search tree insertion method doesn't work

I want to implement a insertion method for a Binary search tree, and come up with a solution below. I know there are plenty of code examples but I wonder what is the problem in my implementation? Or is there a problem? When I had traced it I thought I have missed something.

public void insertBST(Node<Double> head, int value){
   if (head == null){
       head = new Node<Double>(value);
       return;
   }
   else {
       if (head.getValue() > value)
           insertBST(head.getLeft(), value);
       else
           insertBST(head.getRight(), value);
   }
 }

Upvotes: 0

Views: 99

Answers (2)

Bernhard Barker
Bernhard Barker

Reputation: 55589

When you reassign a passed parameter, you're only changing the local variable, not the value passed to the function. You can read this question for more information - Is Java "pass-by-reference"? This is Java, right? Either way, a similar argument likely applies.

This is the problem with this line of code:

head = new Node<Double>(value);

You aren't changing the value passed into the function, so you never add to the tree.

You have two alternatives here, either the option presented by amdorra, or returning the current node:

public void insertBST(Node<Double> current, int value)
{
   if (current == null)
   {
       return new Node<Double>(value);
   }
   else
   {
       if (head.getValue() > value)
           head.setLeft(insertBST(head.getLeft(),value));
       else
           head.setRight(insertBST(head.getRight(),value));
       return current;
   }
}

To call the function, you can simply say:

root = insertBST(root, value);

With alternatives, the root will have to be handled as a special case.

Upvotes: 2

amdorra
amdorra

Reputation: 1556

at the beginning of you function you are adding the new Node to a part you will never have access to outside this function

so i will assume that your Node class looks like the following

Class Node{
    private Node left;
    private Node right;
    //constructor, setters and getters and stuff
}

you could modify your code to look like the following:

if (head.getValue() > value){
    if(head.getLeft == null) {
        head.setLeft(new Node<Double>(value));
        return;
    }
    insertBST(head.getLeft(),value);
}
else{
    if(head.getRight == null) {
        head.setRight(new Node<Double>(value));
        return;
    }
    insertBST(head.getRight(),value);
}

you should also remove this part if (head==null) and always make sure you are sending a valid Node to the first call

Upvotes: 1

Related Questions