Null pointer exception when proving min heap in a binary tree

Question

This code is to find out if the binary tree is min heap or not, I keep getting a NullPointerException at the 3rd if statement in public static boolean isMinHeap, I am unsure as to why I keep getting this exception since I thought the code would be valid due to the above break.

public class ArrayHeapChecker {
public static boolean isBinaryTree(Integer[] array) {
    for (int i = 1; i < array.length; i++){
        if (array[i] != null && array [(i-1)/ 2] == null)   {
            return false;
        }
    }
    return true;
}
public static boolean isCompleteBinaryTree(Integer[] array) {
    if(!isBinaryTree(array)) {
        return false;
    }

    for (int i = 0; i < array.length - 1; i++)  {
        if ((i % 2 == 0) && array[i] == null && array[i + 1] != null)   {
            return false;
        }
        if ((i % 2 != 0) && array[i] == null && array[i + 1] != null)   {
            return false;
        }
    }

    return true;
}
public static boolean isMinHeap(Integer[] array) {
    if(!isCompleteBinaryTree(array)) {
        return false;
    }
    for (int i = 0; i < array.length - 1; i++)  {
        if (array[i] == null)   {
            break;
        }
        if (array.length <= ((2*i) + 2))    {
            break;
        }
        if (array[(i * 2) + 1] == null || array[(i * 2) + 2] == null)   {
            break;
        }
        if (array[i] > array[(i * 2) + 1] || array[i] > array[(i * 2) + 2]) {
            return false;
        }
    }
    return true;
}
}

What do you pass for the array? Could it be `null` by any chance? — Sergey Kalinichenko, Sep 04 '16 at 12:57
@dazito yes it is but with the above code, I believe it would be fine. — Ryota, Sep 04 '16 at 13:11
@StephenC sorry, I meant the 3rd if statement in the last method (isMinHeap) — Ryota, Sep 04 '16 at 13:12
@acm I have some of the stacktrace if it helps java.lang.NullPointerException at ArrayHeapChecker.isMinHeap(ArrayHeapChecker.java:36) at TestArrayHeapChecker.testisMinHeap_ArraySizeSeven(TestArrayHeapChecker.java:188) — Ryota, Sep 04 '16 at 13:17
@OldProgrammer I believe so, It's homework that is submitted into an automatic program and I believe the automated program acts as a debugger — Ryota, Sep 04 '16 at 13:19
If the array passed to `isMinHeap` doesn't have every element filled in, that may be the cause of the NPE... — Kevin Anderson, Sep 04 '16 at 13:25
@KevinAnderson That shouldn't be the case because the code in the 2nd method ensures that it is a complete binary tree. — Ryota, Sep 04 '16 at 13:34
@Ryota - I think that you will find that Kevin is correct. A non-null entry in the array is the only way that you can get an NPE in that if statement. Check the logic of the `isBinaryTree` and `isCompleteBinaryTree` methods carefully. Then check the logic of the `if` statement where the NPE is happening. — Stephen C, Sep 04 '16 at 14:03
@StephenC Thank you for your advice! I added simple if statements in my MinHeap method to check for null values and it now works! — Ryota, Sep 04 '16 at 14:36
@KevinAnderson You were right, my assumption that a complete binary tree would only contain values that weren't null was false. Thank you for the insight! — Ryota, Sep 04 '16 at 14:38

acm · Answer 1 · 2016-09-04T14:25:01.810

0

Your are not checking that elements in your array are not null. You are only checking the following array[i] != null && array [(i-1)/ 2] == null in ArrayHeapChecker#isBinaryTree. Which does not protect you from a NPE when comparing an Integer to null. E.g. your code will fail for the following input: new Integer[]{1, 2, 3, 4, 5, 6, null}. I don't suggest you a fix because it depends on your requirements but your check is not strict enough.

To be more precise, as it is right now, your code will fail whenever you have an array with odd length which last element is null, except when lenght == 1.

edited Sep 04 '16 at 14:25

answered Sep 04 '16 at 14:11

acm

2,086
3
16
34

Thanks for the advice, the visual stimulus gave me an idea and it worked! I added simple if statements to check for null values and it worked perfectly! – Ryota Sep 04 '16 at 14:34
Glad it help. Anyway, you should consider refactoring because so many `return` clauses nested in `if` and `for` statements are making your code really hard to understand. Ah! you should not edit your question to include the answer, if people read as it is in your edit won't understand the actual question in the first place. – acm Sep 04 '16 at 14:50

Null pointer exception when proving min heap in a binary tree

1 Answers1