Module 6 · Interactive topic

Huffman Trees

Short codes for frequent letters

Normal text uses 8 bits for every letter. Huffman coding counts how often each letter appears and builds a tree so that frequent letters get short codes and rare letters get long ones. Build the tree, then encode a text into bits and decode the bits back.

  • Greedyalways join the two smallest counts
  • Coderoot → leaf path: left 0, right 1
  • Prefix-freeno code starts another code
Huffman Tree Ready
letters 11
different 5
bits 23
  • 5how often the letter appears

Ready

Comparisons 0 Shifts 0
Ready

Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

What does a Huffman node store?

A leaf stores a letter and how many times it appears. An inner node stores only a count — the sum of its children. The tree is FULL: every inner node has exactly two children. Letters live only in the leaves, which is why no code can be the beginning of another code.

struct Node {
    char ch;              // the letter (leaves only)
    int freq;             // how often it appears
    struct Node *left;    // edge labelled 0
    struct Node *right;   // edge labelled 1
};

// ABRACADABRA:  A 5, B 2, R 2, C 1, D 1
// codes:  A = 0   B = 110   R = 111
//         C = 100 D = 101   → 23 bits, not 88

1. Count

  1. Count how often each letter appears.
  2. Every letter becomes a one-node tree.
  3. Put all trees in a priority queue…
  4. …with the smallest count first.

2. Merge

  1. Take out the two smallest trees.
  2. Make a new node: count = their sum.
  3. First one = left child, second = right child.
  4. Put it back; repeat until one tree is left.

3. Read the codes

  1. Walk from the root to every leaf.
  2. Going left adds a 0, going right adds a 1.
  3. Frequent letters sit high → short codes.
  4. Rare letters sit deep → long codes.

4. Encode

  1. Replace every letter by its code.
  2. Write the codes one after another.
  3. No separators are needed.
  4. Total bits = Σ count × code length.

5. Decode

  1. Start at the root.
  2. Bit 0 → go left, bit 1 → go right.
  3. At a leaf, write its letter…
  4. …and jump back to the root.

Why it works

  1. Letters are only in leaves → prefix-free codes.
  2. Joining the two smallest is a greedy choice…
  3. …that is proven to give the fewest total bits.
  4. Used inside ZIP, JPEG, PNG and MP3.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 HUFFMAN(letters with counts)
2 Q ← priority queue (smallest count first)
3 for each letter c: add a leaf (c, count[c]) to Q
4 while Q has more than one tree
5 left ← REMOVE-MIN(Q)
6 right ← REMOVE-MIN(Q)
7 add new Node(left.freq + right.freq, left, right) to Q
8 return REMOVE-MIN(Q) // the root
Complexity

How fast is each operation?

k = number of different letters, n = length of the text (or of the bits). With a min-heap each of the k − 1 merges costs O(log k).

Operation Best Average Worst Speed
Count letters O(n) O(n) O(n) Grows with n
Build the tree (heap) O(k log k) O(k log k) O(k log k) Grows with n
Encode O(n) O(n) O(n) Grows with n
Decode (per bit) O(1) O(1) O(1) Instant

ABRACADABRA: fixed-length vs Huffman codes

Letter Count ASCII code Huffman code Bits (Huffman)
A 5 01000001 0 5 × 1 = 5
B 2 01000010 110 2 × 3 = 6
R 2 01010010 111 2 × 3 = 6
C 1 01000011 100 1 × 3 = 3
D 1 01000100 101 1 × 3 = 3
Total 11 88 bits — 23 bits (74% smaller)

Even a 3-bit fixed code (enough for 5 letters) would need 33 bits.

Why prefix-free matters

Codes Bits 0110 Can it be decoded?
A = 0, B = 01, C = 10 (not prefix-free) A C A? or B C? … No — 0 is the start of 01
A = 0, B = 10, C = 11 (Huffman) A · C · A Yes — exactly one way
Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 6 correct
Question 1

Which two trees does Huffman's algorithm join at every step?

Question 2

A letter appears very often. Where will it be in the Huffman tree?

Question 3

Codes are A = 0, B = 10, C = 11. What does 11010 decode to?

Question 4

Why can Huffman bits be decoded without separators between letters?

Question 5

The text has 6 different letters. How many merges does building the tree need?

Question 6

Counts: A 5, B 2, R 2, C 1, D 1. How many bits does A need?

Assessment

Trees quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic Expression Trees Next topic → Binary Search Trees