Huffman Encoding in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Huffman Tree Construction

Given the following frequencies for characters, what is the total weight of the root node after building the Huffman tree?

Characters and frequencies: A=5, B=9, C=12, D=13, E=16, F=45

DSA Java

import java.util.*;

class Node implements Comparable<Node> {
    int freq;
    char ch;
    Node left, right;

    Node(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }

    Node(int freq, Node left, Node right) {
        this.freq = freq;
        this.left = left;
        this.right = right;
    }

    public int compareTo(Node other) {
        return this.freq - other.freq;
    }
}

public class HuffmanTree {
    public static Node buildTree(Map<Character, Integer> freqMap) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            pq.add(new Node(entry.getKey(), entry.getValue()));
        }

        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node(left.freq + right.freq, left, right);
            pq.add(parent);
        }

        return pq.poll();
    }

    public static void main(String[] args) {
        Map<Character, Integer> freqMap = new HashMap<>();
        freqMap.put('A', 5);
        freqMap.put('B', 9);
        freqMap.put('C', 12);
        freqMap.put('D', 13);
        freqMap.put('E', 16);
        freqMap.put('F', 45);

        Node root = buildTree(freqMap);
        System.out.println(root.freq);
    }
}

A 100

B 90

C 45

D 50

💡 Hint

Sum all frequencies and check how Huffman tree merges nodes.

The total frequency sum is 5+9+12+13+16+45 = 100. The root node frequency equals the sum of all frequencies.

🧠 Conceptual

intermediate

Understanding Huffman Code Lengths

In Huffman encoding, which character will always have the longest code?

A The character with the highest frequency

B The character with the lowest frequency

C The character in the middle frequency range

D All characters have codes of the same length

💡 Hint

Think about how Huffman tree places characters with different frequencies.

Characters with lower frequency are placed deeper in the Huffman tree, resulting in longer codes.

🔧 Debug

advanced

Identify the Error in Huffman Encoding Code

What error will this code produce when building a Huffman tree?

DSA Java

import java.util.*;

class Node implements Comparable<Node> {
    int freq;
    char ch;
    Node left, right;

    Node(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }

    Node(int freq, Node left, Node right) {
        this.freq = freq;
        this.left = left;
        this.right = right;
    }

    public int compareTo(Node other) {
        return other.freq - this.freq; // Descending order
    }
}

public class HuffmanTree {
    public static Node buildTree(Map<Character, Integer> freqMap) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            pq.add(new Node(entry.getKey(), entry.getValue()));
        }

        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node(left.freq + right.freq, left, right);
            pq.add(parent);
        }

        return pq.poll();
    }
}

A ClassCastException due to missing Comparator

B The code will build the tree correctly with no errors

C NullPointerException when polling from PriorityQueue

D The PriorityQueue will behave as a max-heap causing incorrect tree structure

💡 Hint

Check the compareTo method and how PriorityQueue orders elements.

The compareTo method returns descending order, but Huffman requires ascending order to build the tree correctly. This causes incorrect tree structure.

🚀 Application

advanced

Huffman Encoding Output Codes

Given the frequencies: A=3, B=2, C=6, D=8, what is the Huffman code for character 'B' after building the tree?

A 10

B 00

C 110

D 111

💡 Hint

Build the Huffman tree step-by-step and assign 0 to left and 1 to right edges.

After building the tree, 'B' is assigned the code '110' based on its position in the tree.

🧠 Conceptual

expert

Huffman Encoding Optimality Proof Concept

Which statement best explains why Huffman encoding produces an optimal prefix code?

A It assigns shorter codes to more frequent characters by building a binary tree with minimum weighted path length

B It uses fixed-length codes for all characters ensuring uniformity

C It sorts characters alphabetically and assigns codes accordingly

D It randomly assigns codes and selects the shortest overall

💡 Hint

Think about how Huffman tree minimizes the total bits used.

Huffman encoding builds a binary tree that minimizes the sum of frequency times code length, producing the shortest average code length.

Practice

1. What is the main purpose of Huffman Encoding in data compression?

easy

A. To sort characters alphabetically

B. To assign shorter codes to more frequent characters

C. To encrypt data for security

D. To assign equal length codes to all characters

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding aims to reduce the total bits used by assigning shorter codes to characters that appear more often.

2. Step 2: Compare options with goal

   Only To assign shorter codes to more frequent characters matches this goal. Options A, B, and C do not describe Huffman Encoding correctly.

3. Final Answer:

   To assign shorter codes to more frequent characters -> Option B

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

Hint: Remember: frequent chars get shorter codes [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing Huffman with encryption
• Assuming it sorts characters alphabetically

2. Which Java data structure is commonly used to build the Huffman tree efficiently?

easy

A. PriorityQueue

B. HashMap

C. ArrayList

D. Stack

Solution

1. Step 1: Identify data structure for minimum frequency extraction

   Huffman tree construction repeatedly extracts two nodes with the smallest frequencies.

2. Step 2: Match data structure to this need

   A PriorityQueue efficiently provides the smallest element each time, making it ideal for this task.

3. Final Answer:

   PriorityQueue -> Option A

4. Quick Check:

   Minimum extraction = PriorityQueue [OK]

Hint: Use PriorityQueue for smallest frequency extraction [OK]

Common Mistakes:

• Using ArrayList which is not efficient for min extraction
• Choosing HashMap which stores key-value pairs, not order
• Selecting Stack which is LIFO, not suitable here

3. What is the output Huffman code for characters given frequencies: A=5, B=9, C=12, D=13, E=16, F=45? (Assuming standard Huffman algorithm)

medium

A. A: 111, B: 110, C: 101, D: 100, E: 0, F: 11

B. A: 0, B: 111, C: 110, D: 10, E: 101, F: 100

C. A: 100, B: 101, C: 110, D: 111, E: 0, F: 11

D. A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies stepwise: (A=5, B=9) -> 14, then combine with C=12, etc., building tree with F=45 as root's child.

2. Step 2: Assign codes from tree paths

   F gets shortest code '0' (highest freq). A and B get longer codes starting with '1100' and '1101' respectively.

3. Final Answer:

   A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0 -> Option D

4. Quick Check:

   Lowest freq get longest codes = A: 1100, B: 1101, C: 100, D: 101, E: 111, F: 0 [OK]

Hint: Lowest freq get longest codes, highest freq shortest [OK]

Common Mistakes:

• Assigning shortest codes to low frequency chars
• Mixing code assignments without tree structure
• Ignoring frequency order in code lengths

4. Identify the error in this Java snippet for building a Huffman tree:

PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node('a', 5));
pq.add(new Node('b', 9));
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(null, left.freq + right.freq);
parent.left = left;
parent.right = right;
pq.add(parent);

medium

A. Node class must implement Comparable for PriorityQueue

B. Cannot add null character to Node

C. PriorityQueue should be initialized with capacity

D. Must poll three nodes before creating parent

Solution

1. Step 1: Check PriorityQueue usage

   PriorityQueue requires elements to be comparable or a comparator provided to order nodes by frequency.

2. Step 2: Verify Node class implementation

   If Node does not implement Comparable or no comparator is given, pq.poll() will throw runtime error.

3. Final Answer:

   Node class must implement Comparable for PriorityQueue -> Option A

4. Quick Check:

   PriorityQueue needs Comparable nodes [OK]

Hint: Ensure Node implements Comparable for PriorityQueue [OK]

Common Mistakes:

• Ignoring Comparable interface requirement
• Thinking null character is invalid here
• Assuming PriorityQueue needs capacity argument

5. Given a string "abbcccdddd", how many bits will Huffman Encoding save compared to fixed-length 3-bit encoding per character?

hard

A. 7 bits saved

B. 10 bits saved

C. 11 bits saved

D. 15 bits saved

Solution

1. Step 1: Calculate fixed-length bits

   String length is 10, fixed-length 3 bits per char, total bits = 10*3 = 30 bits.

2. Step 2: Calculate Huffman bits

   Frequencies: a=1, b=2, c=3, d=4. Huffman codes: a:100 (3 bits), b:101 (3), c:11 (2), d:0 (1). Total bits = (1*3) + (2*3) + (3*2) + (4*1) = 3 + 6 + 6 + 4 = 19 bits.

3. Step 3: Calculate bits saved

   Bits saved = 30 - 19 = 11 bits.

4. Final Answer:

   11 bits saved -> Option C

5. Quick Check:

   Fixed 30 bits - Huffman 19 bits = 11 bits saved [OK]

Hint: Calculate fixed bits minus Huffman bits for savings [OK]

Common Mistakes:

• Not counting frequencies correctly
• Using wrong bit length for fixed encoding
• Miscomputing total Huffman bits