Could anyone tell me why my code is producing an error?

Question

I have a Huffman Tree, and a character, and I want to return what that character's encoding within the Huffman Tree should be.

I've implemented it using the breadth-first traversal method, and each time I'm checking the left and right tree, I'm checking if the tree's data is equal to character I'm looking for. Each time I go right or left, though, I add 0 or 1 to the encoding so far. Eventually, when I find the character equal to the tree's data, I return that tree's encoding value.

Code:

    public static String findCharEncoding(BinaryTree<CharProfile> bTree, char character) {
        Queue<BinaryTree<CharProfile>> treeQueue = new LinkedList<BinaryTree<CharProfile>>();

        // Create a TreeWithEncoding object from the given arguments and add it to the queue
        treeQueue.add(bTree);

        while (!treeQueue.isEmpty()) {
            BinaryTree<CharProfile> t = treeQueue.remove();

->          if (t.getLeft().getData().getCharacter() == character) {
                return t.getLeft().getData().getEncoding();
            }
            if (t.getLeft() != null) {
                t.getLeft().getData().setEncoding(t.getLeft().getData().getEncoding() + "0");
                treeQueue.add(t.getLeft());
            }

            if (t.getRight().getData().getCharacter() == character) {
                return t.getRight().getData().getEncoding();
            }
            if (t.getRight() != null) {
                t.getRight().getData().setEncoding(t.getRight().getData().getEncoding() + "1");
                treeQueue.add(t.getRight());
            }
        }

        // If it gets to here, the while loop was unsuccessful in finding the encoding
        System.out.println("Unable to find.");
        return "-1";
    }

Which I've implemented as follows:

        for (int i = 0; i < charOccurrences.size(); i++) {
            char character = charOccurrences.get(i).getCharacter();

            charOccurrences.get(i).setEncoding(findCharEncoding(huffmanTree, character));
            System.out.println(charOccurrences.get(i).getEncoding());
        }

CharProfile is a custom class that holds the character value, the probability of the character and the encoding.

It keeps returning a NullPointerExceptionError at the line if (t.getLeft().getData().getCharacter() == character) {, which I've indicated with an arrow. I've tried and tried, but I can't seem to figure out why.

Probably your `t.getData()` is null. You have put a check around `2 if's` and remaining `two if's` are used `bare`. You should enclose them too inside a check for `if (t.getData() != null)`. — Rohit Jain, Nov 05 '12 at 15:45

score 1 · Accepted Answer · answered Nov 05 '12 at 15:44

1

Either t is null or t.getLeft() returns null or t.getLeft().getData() returns null. As we only see the code you show is, it's your job to debug that.

You could insert this a line above the error:

if (t == null) {
    System.out.println("t = null");
} else if (t.getLeft() == null) {
    System.out.println("t.getLeft() returns null");
} else if (t.getLeft().getData() == null) {
    System.out.println("t.getLeft().getData() returns null");
}

answered Nov 05 '12 at 15:44

jlordo

37,490
6
58
83

`t` cannot be null, as the check is performed in the `while` only. – Rohit Jain Nov 05 '12 at 15:47
t.getLeft().getData()( is null, but I can't place why. – Doug Smith Nov 05 '12 at 15:57
We don't see the relevant part of the code, to determine why this method returns `null`. – jlordo Nov 05 '12 at 16:01

score 0 · Answer 2 · answered Nov 05 '12 at 15:54

As pointed out in a comment, you're checking for whether t.getLeft() returns null at one point but not at others. Also, personally, I just hate code that keeps calling the same get methods over and over. I'd probably take this section:

        if (t.getLeft().getData().getCharacter() == character) {
            return t.getLeft().getData().getEncoding();
        }
        if (t.getLeft() != null) {
            t.getLeft().getData().setEncoding(t.getLeft().getData().getEncoding() + "0");
            treeQueue.add(t.getLeft());
        }

and rewrite it as:

left = t.getLeft();
if ( left != null ) {
  data = t.getData();
  encoding = data.getEncoding();
  if ( data.getCharacter() == character ) {
    return encoding;
  else {
    data.setEncoding( encoding + "0" );
    treeQueue.add( left )
  }
}

(I've left out type declarations for the variables I've added, since I'm not sure of the right type names.)

This should avoid the NullPointerException if t.getLeft() is what's returning null; otherwise you should at least see more clearly which reference is null when the exception happens since you won't have multiple dereferences in one line. The section for the right side can be rewritten the same way (and in fact it looks like you could make one method that you simply pass the left and right values to, since you do the same thing for both).

t.getLeft().getData() is what returns the error. – Doug Smith Nov 05 '12 at 16:04 — Doug Smith, Nov 05 '12 at 16:04

Could anyone tell me why my code is producing an error?

2 Answers2