Binary search tree insertion method doesn't work

Question

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

pleas add the `addNode` code to your question so I can help you — amdorra, Nov 17 '13 at 21:20
One obvious problem is that if `head` is `null` then you are only assigning the new `Node` to the local `head`, which has no effect outside this function. — Arkku, Nov 17 '13 at 21:21
@death7eater: i have updated my answer please check and tell me if you have any other questions. — amdorra, Nov 17 '13 at 21:47
Remember to add a language tag to the question. This question is very much language-specific. — Bernhard Barker, Nov 18 '13 at 00:48

score 2 · Answer 1 · edited May 23 '17 at 10:25

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.

amdorra · Answer 2 · 2013-11-17T21:43:34.020

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

Binary search tree insertion method doesn't work

2 Answers2