Null-Pointer in recursively search function after return

Question

I have a class that uses an internal binary tree as a data structure. I have a weird problem. I'm recursively looking for a specific node. If the node is found I want the code to return the reference to it. The problem: After return it's always null! But why?

private HeapNode getHeapNode(double key) {
    //ELEMENT IS NOT AVAILABLE HERE, NULL-Pointer, ALWAYS
    return getHeapNodeRec(key, rootHeapNode);
}

private HeapNode getHeapNodeRec(double key, HeapNode curr) {
    if (curr == null) {
        return null;
    }
    if (curr.getKey() == key) {
        //ELEMENT IS AVAILABLE HERE, I can access its data!
        return curr;
    }
    else {
        getHeapNodeRec(key, curr.getLeft());
        getHeapNodeRec(key, curr.getRight());
    }
    return null;
}

What is the purpose of the return value, when you **discard the return value** in the recursive calls? — Andreas, Jul 27 '16 at 21:17
this should never return null if the key is in the tree because of return curr;? — phip1611, Jul 27 '16 at 21:18
Then I would suspect it's not finding the key if you are sure that it will do that. — Rabbit Guy, Jul 27 '16 at 21:18
@blahfunk It likely is finding the key, but not on the root node, so it's in a recursive call, and the recursive calls discard the return value and return null instead. Oops!!! — Andreas, Jul 27 '16 at 21:19
The "Return" only goes up a single level of recursion. When you return return `curr`, that value is just passed to the calling function - usually the next level up of `getHeapNodeRec`, which then discards it and proceeds to return null. — Edward Peters, Jul 27 '16 at 21:21
@Andreas I don't think this is a duplicate of `What is a NullPointerException, and how do I fix it?` — Sam I am says Reinstate Monica, Jul 27 '16 at 21:21
@Andreas there is no NPE thrown, he's just returning `null` when he shouldn't — Jeeter, Jul 27 '16 at 21:22
The dup is about how to find the source of a null value (the cause of NPE), so the answers in the dup are very on-point for this question: *Why do I have a null value, and how do I fix it?* — Andreas, Jul 27 '16 at 21:24

score 1 · Accepted Answer · answered Jul 27 '16 at 21:39

The reason you’re getting null is because you’re tossing the node away after you start stepping back out:

else {
    getHeapNodeRec(key, curr.getLeft());
    getHeapNodeRec(key, curr.getRight());
}
return null;

You search the left and the right nodes, but then after getting the results of that search, you don’t preserve the result, and just return null, propagating null all the way back up to the root call.

What you should do is something along the lines of:

else {
    HeapNode leftResult = getHeapNodeRec(key, curr.getLeft());
    if (leftResult != null) { 
        return leftResult; 
    }

    HeapNode rightResult = getHeapNodeRec(key, curr.getRight());
    if (rightResult != null) { 
        return rightResult; 
     }
}

thanks a lot. I'm sorry, I sometimes still have problems with recursion. — phip1611, Jul 29 '16 at 08:46

score 0 · Answer 2 · answered Jul 27 '16 at 21:39

You need to return the value that you are recursively fetching, like so.

private HeapNode getHeapNode(double key) {
    //ELEMENT IS NOT AVAILABLE HERE, NULL-Pointer, ALWAYS
    return getHeapNodeRec(key, rootHeapNode);
}

private HeapNode getHeapNodeRec(double key, HeapNode curr) {
    if (curr == null) {
        return null;
    }
    if (curr.getKey() == key) {
        //ELEMENT IS AVAILABLE HERE, I can access its data!
        return curr;
    }
    else {
        if (getHeapNodeRec(key, curr.getLeft()) != null) {
            return curr.getLeft();
        }
        if (getHeapNodeRec(key, current.getRight()) != null) {
            return curr.getRight();
        }
    }
    return null;
}

Null-Pointer in recursively search function after return

2 Answers2