Could anyone tell me why my code for this Huffman encoding algorithm 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, other than the fact that it's t.getLeft().getData() that's returning the error, not the whole thing, or t.getLeft(), but I still can't figure out why.

Start by using your debugger to step into `getData()` and find out why it is returning `null` when you don't expect it to. — Code-Apprentice, Nov 06 '12 at 03:22
The problem finding the error may be a matter of looking in the wrong place. The quoted code depends on a tree node always having non-null data, so that if t.getRight() is not null, neither is t.getRight().getData(). Maybe the tree building is getting that wrong. — Patricia Shanahan, Nov 06 '12 at 03:29

score 1 · Accepted Answer · answered Nov 06 '12 at 04:43

If the left or right tree branch can actually be null--which, if this is Huffman, should probably only be happening at the leaf nodes--why do you call getData on them before you check? That would definitely cause a NullPointerExeption.

if (t.getLeft() != null) {
  // check nullity and THEN check match
  if (t.getLeft().getData().getCharacter() == character) {
    return t.getLeft().getData().getEncoding();
  }
  t.getLeft().getData().setEncoding(t.getLeft().getData().getEncoding() + "0");
  treeQueue.add(t.getLeft());
}

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

p.s. You also might want to avoid returning "-1" if you would otherwise return a bitstring of 0s and 1s, and avoid setting the tree nodes' encoding every time you findCharEncoding, but that's just a wild guess. :)

Could anyone tell me why my code for this Huffman encoding algorithm is producing an error?

1 Answers1