Huffman Encoding in DSA Typescript

Mental Model

Huffman encoding builds a tree to assign shorter codes to frequent letters and longer codes to rare letters, saving space when storing data.

Analogy: Imagine packing a suitcase where you put your most used clothes on top for easy access and less used clothes at the bottom; Huffman encoding puts frequent letters closer to the root for shorter codes.

Characters with frequencies:
[a:5] [b:9] [c:12] [d:13] [e:16] [f:45]

Initial nodes:
[a:5]  [b:9]  [c:12]  [d:13]  [e:16]  [f:45]

After building tree:
          [100]
         /     \
     [45:f]    [55]
              /    \
          [25]      [30]
         /   \     /   \
     [12:c][13:d][14]  [16:e]
                  /  \
               [5:a][9:b]

Dry Run Walkthrough

Input: characters with frequencies: a=5, b=9, c=12, d=13, e=16, f=45

Goal: build Huffman tree and assign codes to each character

Step 1: Create leaf nodes for each character with their frequencies

[a:5] [b:9] [c:12] [d:13] [e:16] [f:45]

Why: We start with all characters as separate nodes to build the tree

Step 2: Pick two nodes with smallest frequencies (a:5, b:9) and merge into new node with freq 14

[14] -> [a:5], [b:9]  [c:12] [d:13] [e:16] [f:45]

Why: Combine smallest nodes to build tree bottom-up

Step 3: Pick next two smallest nodes (c:12, d:13) and merge into new node with freq 25

[14] -> [a:5], [b:9]  [25] -> [c:12], [d:13]  [e:16] [f:45]

Why: Continue combining smallest nodes

Step 4: Pick two smallest nodes (14, 16) and merge into new node with freq 30

[25] -> [c:12], [d:13]  [30] -> [14], [e:16]  [f:45]

Why: Merge combined node with next smallest leaf

Step 5: Pick two smallest nodes (25, 30) and merge into new node with freq 55

[55] -> [25], [30]  [f:45]

Why: Merge internal nodes to build upper tree

Step 6: Pick two remaining nodes (45, 55) and merge into root node with freq 100

[100] -> [f:45], [55]

Why: Final merge forms the root of Huffman tree

Step 7: Assign codes by traversing tree: left edge adds '0', right edge adds '1'

Codes: f=0, c=100, d=101, a=1100, b=1101, e=111

Why: Assign unique prefix codes based on tree path

Result:

Huffman codes:
f:0
c:100
d:101
a:1100
b:1101
e:111

Annotated Code

DSA Typescript

class Node {
  char: string | null;
  freq: number;
  left: Node | null;
  right: Node | null;
  constructor(char: string | null, freq: number, left: Node | null = null, right: Node | null = null) {
    this.char = char;
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

function buildHuffmanTree(chars: string[], freqs: number[]): Node | null {
  let nodes: Node[] = [];
  for (let i = 0; i < chars.length; i++) {
    nodes.push(new Node(chars[i], freqs[i]));
  }

  if (nodes.length === 0) return null;

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq); // sort by freq ascending
    const left = nodes.shift()!; // smallest freq
    const right = nodes.shift()!; // next smallest freq
    const merged = new Node(null, left.freq + right.freq, left, right);
    nodes.push(merged);
  }

  return nodes[0];
}

function generateCodes(node: Node | null, prefix: string, codes: Map<string, string>) {
  if (!node) return;
  if (node.char !== null) {
    codes.set(node.char, prefix);
  } else {
    generateCodes(node.left, prefix + '0', codes);
    generateCodes(node.right, prefix + '1', codes);
  }
}

// Driver code
const chars = ['a', 'b', 'c', 'd', 'e', 'f'];
const freqs = [5, 9, 12, 13, 16, 45];
const root = buildHuffmanTree(chars, freqs);
const codes = new Map<string, string>();
generateCodes(root, '', codes);
for (const c of chars) {
  console.log(`${c}:${codes.get(c)}`);
}

nodes.sort((a, b) => a.freq - b.freq);

sort nodes by frequency ascending to pick smallest two

const left = nodes.shift()!; const right = nodes.shift()!;

remove two smallest nodes to merge

const merged = new Node(null, left.freq + right.freq, left, right);

create new internal node with combined frequency

nodes.push(merged);

add merged node back to list for next iteration

if (node.char !== null) { codes.set(node.char, prefix); }

assign code to leaf node character

generateCodes(node.left, prefix + '0', codes); generateCodes(node.right, prefix + '1', codes);

traverse left and right children adding '0' or '1' to code

Output

a:1100

b:1101

c:100

d:101

e:111

f:0

Complexity Analysis

Time: O(n log n) because we sort the list of nodes repeatedly while building the tree

Space: O(n) for storing nodes and codes for each character

vs Alternative: Compared to fixed-length encoding which uses same length codes, Huffman reduces average code length but requires tree building overhead

Edge Cases

empty input arrays

returns undefined or null tree, no codes generated

DSA Typescript

if (nodes.length === 0) return null;

single character input

tree is single node, code assigned as empty string

DSA Typescript

if (node.char !== null) { codes.set(node.char, prefix); }

all characters have same frequency

tree built normally, codes assigned but lengths may be similar

DSA Typescript

nodes.sort((a, b) => a.freq - b.freq);

When to Use This Pattern

When you need to compress data by assigning variable-length codes based on frequency, reach for Huffman Encoding because it builds an optimal prefix code tree.

Common Mistakes

Mistake: Not sorting nodes by frequency before merging
Fix: Always sort nodes ascending by frequency before picking two smallest to merge

Mistake: Assigning codes only at root or internal nodes
Fix: Assign codes only at leaf nodes where character is stored

Mistake: Using fixed-length codes instead of variable-length
Fix: Use tree traversal to assign variable-length codes based on path

Summary

Builds a tree to assign shorter codes to frequent characters and longer codes to rare ones for efficient data compression.

Use when you want to compress data by encoding characters with variable-length binary codes based on frequency.

The key insight is merging the two least frequent nodes repeatedly to build a prefix-free binary tree that minimizes total code length.

Practice

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

easy

A. To sort characters alphabetically

B. To assign equal length codes to all characters

C. To encrypt data for security

D. To assign shorter codes to more frequent characters

Solution

1. Step 1: Understand Huffman Encoding goal

   Huffman Encoding aims to reduce the total bits used by giving shorter codes to frequent characters.

2. Step 2: Compare options with this goal

   Only To assign shorter codes to more frequent characters matches this goal. Others describe different or incorrect purposes.

3. Final Answer:

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

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 Huffman with encryption
• Assuming it sorts characters alphabetically

2. Which TypeScript data structure is best suited to build the priority queue for Huffman Encoding?

easy

A. Array with manual sorting

B. Min-Heap

C. Set

D. Map

Solution

1. Step 1: Identify priority queue needs

   Huffman Encoding requires repeatedly extracting the smallest frequency node efficiently.

2. Step 2: Choose data structure for efficient min extraction

   Min-Heap allows quick access and removal of the smallest element, ideal for this use.

3. Final Answer:

   Min-Heap -> Option B

4. Quick Check:

   Priority queue = Min-Heap for Huffman [OK]

Hint: Use Min-Heap for efficient smallest element extraction [OK]

Common Mistakes:

• Using Set which has no order
• Using Map which is key-value, not priority queue
• Using Array without sorting is inefficient

3. What is the output Huffman code for characters {a:5, b:9, c:12, d:13, e:16, f:45} after building the Huffman tree?

medium

A. { 'f': '1', 'c': '00', 'd': '01', 'a': '100', 'b': '101', 'e': '110' }

B. { 'a': '0', 'b': '10', 'c': '110', 'd': '1110', 'e': '1111', 'f': '101' }

C. { 'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111' }

D. { 'a': '111', 'b': '110', 'c': '10', 'd': '0', 'e': '101', 'f': '100' }

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies stepwise: (a=5,b=9)->14, (c=12,d=13)->25, then combine 14 and 16 (e) and so on, finally f=45 is highest frequency with shortest code.

2. Step 2: Assign codes from tree paths

   Left edges as '0', right edges as '1' produce codes: f='0', c='100', d='101', a='1100', b='1101', e='111'.

3. Final Answer:

   { 'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111' } -> Option C

4. Quick Check:

   Highest freq 'f' gets shortest code '0' [OK]

Hint: Highest frequency gets shortest code '0' in Huffman [OK]

Common Mistakes:

• Assigning codes without building tree
• Mixing left/right edge bits
• Ignoring frequency order

4. Given this TypeScript snippet for Huffman tree node insertion, what is the bug?

class Node {
  constructor(public char: string | null, public freq: number, public left: Node | null = null, public right: Node | null = null) {}
}

function insertNode(queue: Node[], node: Node) {
  queue.push(node);
  queue.sort((a, b) => a.freq - b.freq);
}

// Usage
const queue: Node[] = [];
insertNode(queue, new Node('a', 5));
insertNode(queue, new Node('b', 9));
insertNode(queue, new Node(null, 14));

medium

A. Sorting after push is inefficient; use a Min-Heap instead

B. Node constructor missing type annotations

C. Function insertNode should remove duplicates

D. queue.sort comparator should be reversed

Solution

1. Step 1: Analyze insertNode function

   It pushes a node then sorts the entire queue array by frequency each time.

2. Step 2: Identify inefficiency

   Sorting the whole array on every insertion is inefficient for large data; a Min-Heap is better for priority queue operations.

3. Final Answer:

   Sorting after push is inefficient; use a Min-Heap instead -> Option A

4. Quick Check:

   Priority queue needs efficient insert and extract [OK]

Hint: Use Min-Heap, not array sort, for priority queue [OK]

Common Mistakes:

• Thinking sorting order is wrong
• Missing inefficiency of sorting whole array
• Confusing type annotations as bug

5. You have a string "aaabbc" and want to encode it using Huffman Encoding. Which of the following is the correct Huffman code assignment and encoded bit string?

hard

A. Codes: {a:'0', b:'10', c:'11'}, Encoded: '000101011'

B. Codes: {a:'10', b:'0', c:'11'}, Encoded: '101010011'

C. Codes: {a:'0', b:'11', c:'10'}, Encoded: '00011110'

D. Codes: {a:'1', b:'0', c:'10'}, Encoded: '1110010'

Solution

1. Step 1: Calculate frequencies

   String "aaabbc" has frequencies: a=3, b=2, c=1.

2. Step 2: Build Huffman tree and assign codes

   Lowest freq c=1 and b=2 combine first, then with a=3. Assign codes: a='0', b='10', c='11'.

3. Step 3: Encode string using codes

   Encoding "aaabbc" = a(3 times) '0 0 0', b(2 times) '10 10', c(1 time) '11' -> '000101011'.

4. Final Answer:

   Codes: {a:'0', b:'10', c:'11'}, Encoded: '000101011' -> Option A

5. Quick Check:

   Freq order a>b>c matches codes and encoding [OK]

Hint: Encode by replacing chars with shortest codes from tree [OK]

Common Mistakes:

• Mixing code assignments
• Encoding with wrong code bits
• Ignoring frequency order in code assignment