Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Huffman Encoding
DSA

Huffman Encoding

Learn how Huffman coding uses a greedy strategy to construct optimal prefix codes.

Huffman Encoding creates a prefix-free binary code with minimum total encoding cost.

The tree grows from repeated two-smallest merges — internal nodes pop in as they’re created:

Huffman Coding

Build an optimal prefix-code tree by repeatedly merging the two smallest frequencies.

Keep all frequencies in a min-heap; repeatedly pop the two smallest, merge them into a parent whose weight is their sum, and push it back. Frequent symbols merge late and stay shallow (short codes); rare ones go deep. The greedy smallest-first merge is provably optimal.

TREE VISUALIZER
Steps –
100f:4555302514e:16c:12d:13a:5b:9
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        heap = all leaf frequencies
                      
                        2
                        while heap.size > 1:
                      
                        3
                          x = pop min; y = pop min
                      
                        4
                          node = new(x + y)
                      
                        5
                          push(node) into heap

The main idea is simple:

Repeatedly merge the two symbols with the smallest frequencies.

Focus on recognizing:

“Frequencies” + “Prefix-free encoding” + “Minimum cost” = Huffman

Pattern Table

PatternTypical QuestionsTrigger
Build Huffman TreeMinimum encoding costMerge two smallest
Generate CodesGet binary codesDFS through the tree
Encode StringConvert text to bitsUse generated codes
Decode StringConvert bits to textTraverse the tree

Mental Trigger

Min-Heap → Take 2 smallest → Merge → Put back → Repeat

1. Generic Huffman Template (Base)

This is the main Huffman template to memorize.

class HuffmanNode implements Comparable<HuffmanNode> {

    char ch;
    int freq;

    HuffmanNode left;
    HuffmanNode right;

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

    public int compareTo(HuffmanNode other) {
        return Integer.compare(this.freq, other.freq);
    }
}

public HuffmanNode buildTree(char[] chars, int[] freqs) {

    PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();

    for (int i = 0; i < chars.length; i++) {
        pq.offer(new HuffmanNode(chars[i], freqs[i]));
    }

    while (pq.size() > 1) {

        HuffmanNode left = pq.poll();
        HuffmanNode right = pq.poll();

        HuffmanNode merged =
                new HuffmanNode('-', left.freq + right.freq);

        merged.left = left;
        merged.right = right;

        pq.offer(merged);
    }

    return pq.poll();
}
import heapq

class HuffmanNode:
    def __init__(self, ch, freq):
        self.ch = ch
        self.freq = freq

        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def build_tree(chars, freqs):
    pq = [HuffmanNode(chars[i], freqs[i]) for i in range(len(chars))]
    heapq.heapify(pq)

    while len(pq) > 1:
        left = heapq.heappop(pq)
        right = heapq.heappop(pq)

        merged = HuffmanNode('-', left.freq + right.freq)

        merged.left = left
        merged.right = right

        heapq.heappush(pq, merged)

    return heapq.heappop(pq)
struct HuffmanNode {
    char ch;
    int freq;

    HuffmanNode* left;
    HuffmanNode* right;

    HuffmanNode(char c, int f)
        : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

HuffmanNode* buildTree(vector<char>& chars, vector<int>& freqs) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;

    for (int i = 0; i < (int)chars.size(); i++) {
        pq.push(new HuffmanNode(chars[i], freqs[i]));
    }

    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();

        HuffmanNode* merged =
                new HuffmanNode('-', left->freq + right->freq);

        merged->left = left;
        merged->right = right;

        pq.push(merged);
    }

    return pq.top();
}
// ponytail: JS has no builtin heap; sort-per-merge keeps the snippet tiny (O(n² log n))
class HuffmanNode {
  constructor(ch, freq) {
    this.ch = ch;
    this.freq = freq;

    this.left = null;
    this.right = null;
  }
}

function buildTree(chars, freqs) {
  const pq = chars.map((ch, i) => new HuffmanNode(ch, freqs[i]));

  while (pq.length > 1) {
    pq.sort((a, b) => a.freq - b.freq);

    const left = pq.shift();
    const right = pq.shift();

    const merged = new HuffmanNode('-', left.freq + right.freq);

    merged.left = left;
    merged.right = right;

    pq.push(merged);
  }

  return pq[0];
}

Everything else in Huffman is built on this tree.

Pattern 1: Build Huffman Tree

What does this do?

Builds the Huffman tree by repeatedly combining the two smallest frequencies.

Example:

A = 5
B = 9
C = 12
D = 13

First:

5 + 9 = 14

Then:

12 + 13 = 25

Then continue until only one tree remains.

What Changed from the Base?

This is the base pattern itself.

The important part is:

HuffmanNode left = pq.poll();
HuffmanNode right = pq.poll();

Take the two smallest nodes.

Then:

HuffmanNode merged =
        new HuffmanNode('-', left.freq + right.freq);

Create a new node containing their combined frequency.

Then:

pq.offer(merged);

Put the merged node back into the min-heap.

Huffman Tree = Min-Heap + Take 2 Smallest + Merge + Push Back

Pattern 2: Generate Huffman Codes

Once the tree is built, traverse it to generate the binary code for every character.

Java Code

public void generateCodes(
        HuffmanNode root,
        String code,
        Map<Character, String> codes) {

    if (root == null) {
        return;
    }

    // Leaf node
    if (root.left == null && root.right == null) {
        codes.put(root.ch, code);
        return;
    }

    generateCodes(root.left, code + "0", codes);

    generateCodes(root.right, code + "1", codes);
}
def generate_codes(root, code, codes):
    if root is None:
        return

    # Leaf node
    if root.left is None and root.right is None:
        codes[root.ch] = code
        return

    generate_codes(root.left, code + "0", codes)

    generate_codes(root.right, code + "1", codes)
void generateCodes(HuffmanNode* root, string code,
                   unordered_map<char, string>& codes) {
    if (root == nullptr) {
        return;
    }

    // Leaf node
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->ch] = code;
        return;
    }

    generateCodes(root->left, code + "0", codes);

    generateCodes(root->right, code + "1", codes);
}
function generateCodes(root, code, codes) {
  if (root === null) {
    return;
  }

  // Leaf node
  if (root.left === null && root.right === null) {
    codes.set(root.ch, code);
    return;
  }

  generateCodes(root.left, code + "0", codes);

  generateCodes(root.right, code + "1", codes);
}

What Changed from the Base?

1. Added recursion

Base:

// Build the tree

Changed:

generateCodes(root.left, code + "0", codes);
generateCodes(root.right, code + "1", codes);

because we need to visit every node in the Huffman tree.

2. Track the current code

Added:

String code

because every left/right decision creates one bit.

left  → 0
right → 1

3. Store codes at leaf nodes

Added:

if (root.left == null && root.right == null) {
    codes.put(root.ch, code);
}

because only leaf nodes represent actual characters.

Generate Codes = DFS + Left → 0 + Right → 1 + Store at leaves

Pattern 3: Encode a String

After generating the Huffman codes, replace each character with its code.

Java Code

public String encode(
        String text,
        Map<Character, String> codes) {

    StringBuilder result = new StringBuilder();

    for (char ch : text.toCharArray()) {
        result.append(codes.get(ch));
    }

    return result.toString();
}
def encode(text, codes):
    result = []

    for ch in text:
        result.append(codes[ch])

    return ''.join(result)
string encode(string& text, unordered_map<char, string>& codes) {
    string result;

    for (char ch : text) {
        result += codes[ch];
    }

    return result;
}
function encode(text, codes) {
  let result = '';

  for (const ch of text) {
    result += codes.get(ch);
  }

  return result;
}

What Changed from the Base?

Added input string

Base:

// Build tree

Changed:

String text

because we now need to encode actual data.

Look up each character

Added:

codes.get(ch)

because the Huffman tree has already given every character its binary code.

Encode = Character → Look up Huffman code → Append bits

Pattern 4: Decode a Huffman String

To decode, start at the root and follow the bits.

0 → left
1 → right

When you reach a leaf, you found one character.

Java Code

public String decode(
        String bits,
        HuffmanNode root) {

    StringBuilder result = new StringBuilder();

    HuffmanNode current = root;

    for (char bit : bits.toCharArray()) {

        if (bit == '0') {
            current = current.left;
        } else {
            current = current.right;
        }

        if (current.left == null &&
            current.right == null) {

            result.append(current.ch);
            current = root;
        }
    }

    return result.toString();
}
def decode(bits, root):
    result = []

    current = root

    for bit in bits:
        if bit == '0':
            current = current.left
        else:
            current = current.right

        if current.left is None and current.right is None:
            result.append(current.ch)
            current = root

    return ''.join(result)
string decode(string& bits, HuffmanNode* root) {
    string result;

    HuffmanNode* current = root;

    for (char bit : bits) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }

        if (current->left == nullptr &&
            current->right == nullptr) {
            result += current->ch;
            current = root;
        }
    }

    return result;
}
function decode(bits, root) {
  let result = '';

  let current = root;

  for (const bit of bits) {
    if (bit === '0') {
      current = current.left;
    } else {
      current = current.right;
    }

    if (current.left === null && current.right === null) {
      result += current.ch;
      current = root;
    }
  }

  return result;
}

What Changed from the Base?

1. Traverse the tree using bits

Added:

if (bit == '0') {
    current = current.left;
} else {
    current = current.right;
}

because each bit tells us which direction to move.

2. Detect a leaf

Added:

if (current.left == null &&
    current.right == null)

because reaching a leaf means one character has been decoded.

3. Return to root

Added:

current = root;

because the next bits represent the next character.

Decode = Bit → Traverse tree → Reach leaf → Output character → Return to root

Huffman Pattern Evolution

Build Tree
    ↓
Min-Heap
    ↓
Take 2 smallest
    ↓
Merge
    ↓
Push back
    ↓
Tree complete
    ↓
DFS
    ↓
Generate 0/1 codes
    ↓
Encode / Decode

Common Mistakes

1. Using a normal queue

Wrong:

Queue<HuffmanNode> queue;

Use:

PriorityQueue<HuffmanNode> pq;

because we always need the two smallest frequencies.

2. Using a max-heap

Huffman needs:

smallest frequency first

So use a min-heap.

3. Forgetting the leaf check

Wrong:

codes.put(root.ch, code);

Not every node represents a character.

Correct:

if (root.left == null && root.right == null) {
    codes.put(root.ch, code);
}

4. Mixing up left and right

Use a consistent rule:

left  → 0
right → 1

5. Forgetting to put the merged node back

After:

left + right

you must:

pq.offer(merged);

Otherwise the algorithm cannot continue.

Recognition Cheat Sheet

If you see…Think…
Frequencies + encodingHuffman
Prefix-free codesHuffman
Minimum encoding costHuffman
Merge two smallestMin-Heap + Greedy
Generate binary codesDFS on Huffman tree
Decode 0/1 stringTraverse Huffman tree

Complexity

For n unique characters:

Build Tree:
O(n log n)

Generate Codes:
O(n)

Space:
O(n)

Simple Mental Model

Take the 2 smallest → Merge them → Repeat → DFS the tree for codes.

My Private Notes

Notes are auto-saved locally to this device.