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.