Java binary search tree loop returning null object reference?

Question

I've written a remove function for a binary search tree that uses a while loop to navigate to the specific node to be removed. However, it's never getting there - it just iterates an unknown number of times and then gives me a NullPointerException.

I was wondering if it was an error in my traversal logic, but it's exactly the same as in my add function, which works perfectly.

void remove(Comparable newObject){
    if (!isEmpty()){
        Node curr = new Node();
    curr = root;
    boolean isFound = false;
    while (!isFound){
        if (curr.data.compareTo(newObject) == 0){
            if (curr.hasChildren()){
                Node replaceNode = new Node();
                if (curr.leftChild == null){
                    replaceNode = curr.rightChild;
                    while (replaceNode.leftChild != null){
                        replaceNode = replaceNode.leftChild;
                    }
                } else {
                    replaceNode = curr.leftChild;
                    while (replaceNode.rightChild != null) {    
                        replaceNode = replaceNode.rightChild;
                    }
                }
                replaceNode.leftChild = curr.leftChild;
                replaceNode.rightChild = curr.rightChild;
                replaceNode.parent = curr.parent;
                curr = replaceNode;
            } else {
                curr.data = null;
                curr.parent = null;
            }
            listSize--;
            isFound = true;
        } else if (curr.data.compareTo(newObject) == 1) {
            curr = curr.leftChild;
        } else {
            curr = curr.rightChild;
        }
    }
    }
}

The data set I'm using yields a root with a left child, and then a right child off of that. The node to be removed is the first (left) child. However, the line that's giving the NullPointerException is

if (curr.data.compareTo(newObject) == 0){

and I'm really not sure at all what's causing this. Any and all help is appreciated greatly.

Possible duplicate of [What is a NullPointerException, and how do I fix it?](https://stackoverflow.com/questions/218384/what-is-a-nullpointerexception-and-how-do-i-fix-it) — Antoniossss, Mar 29 '19 at 07:26

score 0 · Answer 1 · answered Mar 29 '19 at 07:42

0

First of all don't initialize the variable as a new Node(), you're creating new Nodes you're not gonna use. Do it more like this:

void remove(Comparable newObject){
    if (!isEmpty()){
        Node curr = root;

and then again your replaceNode:

if (curr.hasChildren()){
    Node replaceNode;

and I think it's not working, because in the end of the code, you rewrite curr to its children, but what if it doesn't have children? Then you try to compare null object with some object and that's why I think it throws NullPointerException.

answered Mar 29 '19 at 07:42

AP11

617
4
11

The thing is, the way my traversal is set up, it shouldn't ever set `curr` to a null node. It should only follow the path of the tree. My data sets are such that I will only ever input nodes that already exist. If the root has a leftChild with a leftChild, then calling remove() on that grandchild for removal should trip the loop with a compareTo value of 1 twice (since the root will be greater than the input node, and the leftChild will be greater than the input node), leaving the iterator at the grandchild node. – Crux_Haloine Mar 29 '19 at 21:42

Java binary search tree loop returning null object reference?

1 Answers1