rogue null pointer in a binary search tree when adding strings

Question

working on homework, here's the code:

public void insert(E value){
        Node addative= new Node(value, null, null);
        Node current=this.root;
        if(current==null){
            this.root = addative;
            size++;
            return;
        }
        System.out.println("root is: "+root.value+" value is: "+value);
        while(true){
            //System.out.println("current is currently: "+current.value);
            if(null==current.lesser)System.out.println("lesser is null");
            else System.out.println("lesser is: "+current.lesser.value);
            if(null==current.greater)System.out.println("greater is null");
            else System.out.println("greater is: "+current.greater.value);

            //if slot is empty and addative belongs here
            if(current.lesser==null&&current.value.compareTo(addative.value)>0){
                System.out.println("was added lesser");
                current.lesser=addative;
                break;
            }

            //if slot is empty and addative belongs here
            if(current.greater==null&&current.value.compareTo(addative.value)<=0){
                System.out.println("was added greater");
                current.greater=addative;
                break;
            }
            System.out.println("here");

            //no valid empty slots ergo continue along tree
            if(current.value.compareTo(addative.value)>0)current=current.lesser;
            if(current.value.compareTo(addative.value)<=0)current=current.greater;
        }
        size++;
        System.out.println("next word");
    }

Here's the print out:

root is: tangerines value is: skeptics lesser is null greater is null was added lesser next word root is: tangerines value is: wombats lesser is: skeptics greater is null was added greater next word root is: tangerines value is: valeting lesser is: skeptics greater is: wombats here lesser is null greater is null was added lesser next word root is: tangerines value is: bubble lesser is: skeptics greater is: wombats here lesser is null greater is null was added lesser next word root is: tangerines value is: pigeonhole lesser is: skeptics greater is: wombats here lesser is: bubble greater is null here

Exception in thread "main" java.lang.NullPointerException
    at BinarySearchTree.insert(BinarySearchTree.java:35)
    at BinarySearchTree.main(BinarySearchTree.java:178)

Line 35 says:

if(null==current.lesser)System.out.println("lesser is null");

am I trying to null reference wrong? I don't understand how this can add 5-10 words and work, but on the 11th time it errors out.

Answer 1

You are assigning null to your current here:

// before adding 'pigeonhole':
             tangerines
    skeptics           wombats
bubble     null    valeting   null

Now, when on 'skeptics', "skeptics".compareTo("pigeonhole") < 0, so you set current = current.greater, i.e. current = null. On the next iteration you call current.lesser, which results in an NPE.

The problem here is that you yourself say 'no valid empty slots' and assign them right after that. You should change your logic so that when you didn't perform insertion on a current level, the current assignment is based not just on a compareTo result, but on entries' null status as well. E.g.:

// pigeonhole < skeptics, hence
if (current > addative && current.lesser != null) {
    current = current.lesser;
}
// and something like that for the 'greater' case

Anyway, you should've used good old pencil-and-paper debugging for this, since this bug can be easily uncovered if you try to manually reproduce the steps. Actually, you should use this method before you start to code an algorithm because it seems that formal assessment of the correctness of your implementations isn't your strongest side yet, and writing down every possible step of your program is the best way to train that skill.