Huffman Encoding in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Huffman Tree Construction

What is the output of the following Rust code that builds a Huffman tree from given character frequencies and prints the root node frequency?

DSA Rust

use std::collections::BinaryHeap;

#[derive(Eq, PartialEq)]
struct Node {
    freq: usize,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.freq.cmp(&self.freq)
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn build_huffman_tree(freqs: &[(char, usize)]) -> Node {
    let mut heap = BinaryHeap::new();
    for &(ch, freq) in freqs {
        heap.push(Node { freq, left: None, right: None });
    }
    while heap.len() > 1 {
        let left = heap.pop().unwrap();
        let right = heap.pop().unwrap();
        let merged = Node {
            freq: left.freq + right.freq,
            left: Some(Box::new(left)),
            right: Some(Box::new(right)),
        };
        heap.push(merged);
    }
    heap.pop().unwrap()
}

fn main() {
    let freqs = [('a', 5), ('b', 9), ('c', 12), ('d', 13), ('e', 16), ('f', 45)];
    let root = build_huffman_tree(&freqs);
    println!("{}", root.freq);
}

A 100

B 45

C 90

D 50

💡 Hint

Sum all frequencies to find the root node frequency.

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

🧠 Conceptual

intermediate

Huffman Encoding Code Length Calculation

Given a Huffman tree built from characters with frequencies [('x', 1), ('y', 1), ('z', 2)], what is the total length of the encoded string for the input "xyzzy"?

A 7 bits

B 9 bits

C 8 bits

D 10 bits

💡 Hint

Calculate the code length for each character based on the Huffman tree and multiply by its occurrences.

The Huffman tree assigns 1 bit to 'z' (highest freq) and 2 bits to 'x' and 'y' (lowest freq). The string "xyzzy" has 1 'x' (2 bits), 2 'y' (4 bits), 2 'z' (2 bits), total 8 bits.

🔧 Debug

advanced

Identify the Error in Huffman Tree Node Comparison

What error will the following Rust code produce when compiling, and why? ```rust use std::collections::BinaryHeap; #[derive(Eq, PartialEq)] struct Node { freq: usize, } impl Ord for Node { fn cmp(&self, other: &Self) -> std::cmp::Ordering { self.freq.cmp(&other.freq) } } impl PartialOrd for Node { fn partial_cmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } fn main() { let mut heap = BinaryHeap::new(); heap.push(Node { freq: 5 }); heap.push(Node { freq: 3 }); while let Some(node) = heap.pop() { println!("{}", node.freq); } } ```

A Runtime panic due to invalid heap state

B Prints frequencies in descending order: 5 then 3

C Compilation error: `Ord` implementation does not define a total order

D Prints frequencies in ascending order: 3 then 5

💡 Hint

Check how the cmp function orders elements in BinaryHeap.

No compilation or runtime error. BinaryHeap is a max-heap that pops the greatest element first. The `cmp` uses `self.freq.cmp(&other.freq)`, so higher freq is greater, printing 5 then 3.

🚀 Application

advanced

Huffman Encoding Map Generation

Which option correctly generates a Huffman encoding map (character to bit string) from a given Huffman tree node in Rust?

DSA Rust

fn generate_codes(node: &Node, prefix: String, codes: &mut std::collections::HashMap<char, String>) {
    if let Some(ch) = node.ch {
        codes.insert(ch, prefix);
    } else {
        if let Some(ref left) = node.left {
            generate_codes(left, prefix.clone() + "0", codes);
        }
        if let Some(ref right) = node.right {
            generate_codes(right, prefix + "1", codes);
        }
    }
}

A Inserts codes only for internal nodes, missing leaf characters

B Appends '1' for left and '0' for right, reversing code bits

C Does not clone prefix when recursing left, causing shared mutable state error

D Correctly traverses tree, appending '0' for left and '1' for right, storing codes

💡 Hint

Check how prefix strings are built and stored for leaf nodes.

Option D correctly clones prefix for left recursion and appends '0' or '1' accordingly, storing codes only at leaf nodes with characters.

🧠 Conceptual

expert

Optimality of Huffman Encoding

Why is Huffman encoding considered optimal for prefix codes when encoding symbols with known frequencies?

A It produces the shortest average code length among all prefix codes for given frequencies

B It guarantees equal length codes for all symbols, simplifying decoding

C It uses fixed-length codes minimizing memory usage

D It encodes symbols in alphabetical order to optimize search

💡 Hint

Think about average code length and prefix property.

Huffman encoding minimizes the weighted average code length for symbols with given frequencies, ensuring no other prefix code can produce a shorter average length.

Practice

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

easy

A. To assign shorter codes to more frequent characters

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding compresses data by giving shorter codes to characters that appear more often.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this goal; others describe different concepts.

3. Final Answer:

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

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

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

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing compression with encryption
• Assuming sorting is the main goal

2. Which Rust data structure is best suited to implement the priority queue needed for Huffman Encoding?

easy

A. BinaryHeap<T>

B. HashMap

C. Vec<T>

D. LinkedList<T>

Solution

1. Step 1: Identify priority queue requirement

   Huffman Encoding needs a structure to get the smallest frequency element quickly.

2. Step 2: Match Rust structures to priority queue

   BinaryHeap<T> is Rust's built-in priority queue supporting efficient min/max operations.

3. Final Answer:

   BinaryHeap<T> -> Option A

4. Quick Check:

   Priority queue = BinaryHeap in Rust [OK]

Hint: Use BinaryHeap for priority queues in Rust [OK]

Common Mistakes:

• Using Vec without sorting for priority queue
• Choosing HashMap which is for key-value pairs
• Using LinkedList which is inefficient here

3. What is the output of the following Rust code snippet that builds a Huffman tree for characters with frequencies: {'a': 5, 'b': 9, 'c': 12}?

use std::collections::BinaryHeap;

#[derive(Eq, PartialEq)]
struct Node {
    freq: usize,
    char_opt: Option<char>,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.freq.cmp(&self.freq) // min-heap behavior
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut heap = BinaryHeap::new();
    heap.push(Node { freq: 5, char_opt: Some('a') });
    heap.push(Node { freq: 9, char_opt: Some('b') });
    heap.push(Node { freq: 12, char_opt: Some('c') });

    let first = heap.pop().unwrap();
    let second = heap.pop().unwrap();

    println!("{} {}", first.freq, second.freq);
}

medium

A. 9 5

B. 12 9

C. 5 9

D. 5 12

Solution

1. Step 1: Understand BinaryHeap with custom Ord

   The cmp reverses order to make a min-heap by frequency, so pop() returns smallest freq first.

2. Step 2: Pop two smallest frequencies

   Frequencies are 5, 9, 12. First pop returns 5, second pop returns 9.

3. Final Answer:

   5 9 -> Option C

4. Quick Check:

   Min-heap pops smallest first = 5 9 [OK]

Hint: Custom Ord reverses cmp for min-heap pop order [OK]

Common Mistakes:

• Assuming BinaryHeap is max-heap by default
• Mixing order of popped elements
• Ignoring custom Ord implementation

4. Identify the bug in this Rust code snippet that tries to build a Huffman tree node by combining two nodes:

struct Node {
    freq: usize,
    left: Option,
    right: Option,
}

fn combine_nodes(left: Node, right: Node) -> Node {
    Node {
        freq: left.freq + right.freq,
        left: Some(Box::new(left)),
        right: Some(Box::new(right)),
    }
}

fn main() {
    let n1 = Node { freq: 3, left: None, right: None };
    let n2 = Node { freq: 4, left: None, right: None };
    let parent = combine_nodes(n1, n2);
    println!("Parent freq: {}", parent.freq);
}

medium

A. Cannot use Box::new with struct Node

B. Missing lifetime annotations for Box<Node>

C. Function should take references, not owned Nodes

D. No bug, code compiles and runs correctly

Solution

1. Step 1: Check ownership and Box usage

   Function takes owned Nodes and boxes them correctly for left and right fields.

2. Step 2: Verify code compiles and runs

   Code compiles and prints combined frequency without errors.

3. Final Answer:

   No bug, code compiles and runs correctly -> Option D

4. Quick Check:

   Ownership and Box usage correct = no bug [OK]

Hint: Owned nodes boxed correctly means no bug here [OK]

Common Mistakes:

• Assuming lifetime needed for Box<Node> here
• Thinking references required instead of ownership
• Believing Box::new cannot wrap structs

5. Given character frequencies {'x': 7, 'y': 3, 'z': 2, 'w': 6}, which of the following Huffman codes is valid and optimal?

hard

A. x: 11, y: 10, z: 0, w: 1

B. x: 0, y: 10, z: 110, w: 111

C. x: 10, y: 0, z: 111, w: 110

D. x: 0, y: 1, z: 10, w: 11

Solution

1. Step 1: Order characters by frequency

   Frequencies: z=2, y=3, w=6, x=7. Huffman assigns shortest codes to highest freq.

2. Step 2: Check code lengths and prefix property

   x: 0, y: 10, z: 110, w: 111 assigns shortest code '0' to x (freq 7), longer codes to lower freq chars, and codes are prefix-free.

3. Final Answer:

   x: 0, y: 10, z: 110, w: 111 -> Option B

4. Quick Check:

   Shortest code to highest freq = x: 0, y: 10, z: 110, w: 111 [OK]

Hint: Shortest code goes to highest frequency char [OK]

Common Mistakes:

• Assigning short codes to low frequency chars
• Ignoring prefix-free property
• Confusing code length order