Infinite Recursion, StackOverError in huffman tree

Question

I am working on a Huffman Encoding program and I am almost finished but I am stuck in an infinite recursion loop. Does anyone have an idea where this is going wrong?

This is the error I am getting:

Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.SingleByteEncoder.encodeLoop(SingleByteEncoder.java:130)
at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:544)
at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:252)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:106)
at java.io.OutputStreamWriter.write(OutputStreamWriter.java:190)
at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:111)
at java.io.PrintStream.write(PrintStream.java:476)
at java.io.PrintStream.print(PrintStream.java:619)
at java.io.PrintStream.println(PrintStream.java:756)
at HuffmanNode.buildTree(hw4.java:63)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)
at HuffmanNode.buildTree(hw4.java:64)

and the output is continually 5:1, 5:4, 5:2, repeating

my datafile looks like this:

a
a
a
a
d
d
d
d
d
d
d
d
k
k
k
k
k
k
f
f
f
f
f
f
h
h
h
h
h
h
b
b
b
b
b
b
b
b
n
n
n
n
n
n
n
e
e
e
e
e
i
i
i
i
i
i
i
i
l
k
j
a
n
s
g
l
k
j
a
s
v
o
i
j
a
s
d
l
k
g
k
n
m
a
s
d
k
l
o
v
h
a
s
d
g
z

and my code is

    import java.util.*;
import java.io.*;

class HuffmanNode implements Comparable<HuffmanNode>{
HuffmanNode right;
HuffmanNode left;
HuffmanNode parent;
int count;          
String letter;

public HuffmanNode(){}

public HuffmanNode (String letter, int count){
this.letter = letter;
this.count = count;
}
public HuffmanNode (String letter, int count, HuffmanNode parent, HuffmanNode left, HuffmanNode right){
    this.letter = letter;
    this.count = count;
    this.left = left;
    this.right = right;
    this.parent = parent;
}

public void setCount(int count){
this.count = count;
}

public int getCount(){
return count;
}

public void setRight(HuffmanNode right){
this.right = right;
}

public HuffmanNode getRight(HuffmanNode right){
return right;
}

public void setLeft(HuffmanNode left){
this.left = left;
}

public HuffmanNode getLeft(HuffmanNode left){
return left;
}       
public void setParent(HuffmanNode right){
this.left = left;
}   
public HuffmanNode getParent(HuffmanNode parent){
return parent;
}

public void buildTree(HuffmanNode node){
    if (node.compareTo(this) <= 0 && left != null){
    System.out.println(node.getCount() + ":" + this.count);
    left.buildTree(node);
    }
    else if (node.compareTo(this) <= 0 && left == null){
    this.left = node;
    node.parent = this;
    }
    else if (node.compareTo(this) > 0 && right != null){
    System.out.println(node.getCount() + ":" +this.count);
    right.buildTree(node);
    }
    else if (node.compareTo(this) > 0 && right == null){
    this.right = node;
    node.parent = this;
    }
}


public int compareTo(HuffmanNode x){
return this.count - x.count;
}
public void genCode(String s){
    if(left != null){
    left.genCode(s + "0");
    }
    if(right != null){
    right.genCode(s + "1"); 
    }
    if (left == null && right == null){
    System.out.println(s);
    }
}
}

public class hw4{
public static void main (String []args)throws IOException{

//ask user to enter file name
System.out.printf("Enter a file location and name to encode [press Enter]: ");
Scanner input = new Scanner(System.in);
String filename = input.next();

//Gets file name from Scanner and checks to see if valid
File file = new File(filename);
//if (!file.isFile()){
//System.out.printf("Enter a file location and name to encode [press Enter]: ");
//}
Scanner text = new Scanner(file);

String[] letters = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
int[] freq = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

String letter;
String tempStr;
int tempInt;

    while(text.hasNext()){
        letter = text.next();
        //System.out.printf("%s\n", letter);

                    char c = letter.charAt(0);
        int index = c - 97;
        freq[index]++;     
    }

    for(int i=0; i <25; i++){
    System.out.printf("%s:%d\n", letters[i], freq[i]);
    }
    System.out.printf("\n");

    for (int n=0; n <25; n++) {
        for (int i=0; i <25; i++) {
            if (freq[i] > freq[i+1]) {
                // exchange elements
                tempInt = freq[i];  
                tempStr = letters[i]; 
                freq[i] = freq[i+1];
                letters[i] = letters[i+1];  
                freq[i+1] = tempInt;
                letters[i+1] = tempStr;
            }
        }   
       } 

    PriorityQueue<HuffmanNode> huffmanList = new PriorityQueue<HuffmanNode>();

    for(int i=0; i <26; i++){
    System.out.printf("%s:%d\n", letters[i], freq[i]);
        if(freq[i] > 0){
        huffmanList.add(new HuffmanNode(letters[i],freq[i]));
        }
    }

    HuffmanNode root = new HuffmanNode();

    while(huffmanList.size() > 1){
    HuffmanNode x = huffmanList.poll();
    HuffmanNode y = huffmanList.poll();
    HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
        if(root == null){
        root = result;
        }
        else{
        root.buildTree(result); 
        }
    huffmanList.add(result);                    
    }
     root.genCode(" ");
}
}

Answer 1

Your tree-building is at fault.

while(huffmanList.size() > 1){
    HuffmanNode x = huffmanList.poll();
    HuffmanNode y = huffmanList.poll();

You take the two lightest trees from the queue,

    HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);

and merge them, forming a tree with the sum of weights as weight - so far, so good.

    if(root == null){     // never happens, but doesn't matter
        root = result;
    }
    else{
        root.buildTree(result);

Then you insert the new-formed tree into the root,

    }
    huffmanList.add(result);                    
}

and add it back into the queue.

Now, let us consider a queue starting with

(a,1), (b,2), (c,3), (d,3), (e,3), ...

root = new HuffmanNode(); set root to (null, 0).

First, the a and b nodes are merged, giving <(a,1) | (-,3) | (b,2)>. Inserting into root produces

         (null,0)
          /    \
        null  (-,3)
              /   \
            (a,1) (b,2)

since 3 > 0. The queue is

<(a,1) | (-,3) | (b,2)>, (c,3), (d,3), (e,3) ...

after inserting the merged tree [the merged tree could also be inserted after a couple of weight-3 nodes, then it would take a bit longer].

Now the two lightest trees are popped and merged, giving

<AB | (-,6) | (c,3)>

(with the abbreviation AB = <(a,1) | (-,3) | (b,2)>). That tree is then inserted into the root tree. 6 > 0, so it's inserted into the right child of root, 6 > 3, so it's inserted into the right child of (-,3), 6 > 2, so it becomes the right child of the (b,2) node. But, the left child of the newly merged tree and the right child of root refer to the same object, so after this insertion, you have

                   __________
                  |          |
                  v          |
    (null,0)   (-,6)         |
    /      \   /   \         |
  null     (-,3)   (c,3)     |
           /   \             |
       (a,1)   (b,2)         |
                   \_________|

a cycle in what's supposed to be a tree. Next, the two nodes (d,3) and (e,3) are popped and merged, giving a tree of weight 6, and when that tree shall be inserted into the root graph, it would loop.

Different insertion behaviour and/or different weights of the letters would change the details, but the fact that after root.buildTree(result); and huffmanList.add(result); the queue contains a reference into the graph topped by root leads to cycles whenever you have enough nodes initially. And once you have enough cycles, the probability that a buildTree() call will not land in an infinite loop is small.

You simply should not call root.buildTree(result). The tree is constructed by simply merging the two lightest from the queue and reinserting the result, until the queue contains only one tree.

while(huffmanList.size() > 1){
    HuffmanNode x = huffmanList.poll();
    HuffmanNode y = huffmanList.poll();
    HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
    huffmanList.add(result);                    
}
root = huffmanList.poll();