---
title: "Algorithm for Huffman code"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:huffman-code-algorithm"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/huffman-code-algorithm
site: BCT Engineering
---

# Algorithm for Huffman code

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2070 Magh, 4 marks
- Video: [Huffman Coding | GeeksforGeeks](https://www.youtube.com/watch?v=0kNXhFIEd_w) — GeeksforGeeks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/huffman-code-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Write an algorithm for constructing a Huffman Code.

## Short answer

Create a leaf for each symbol and insert into a min-heap. Repeatedly extract the two smallest-weight nodes, combine as children of a new node with their summed weight, and reinsert. The final tree gives codes by assigning 0 to left, 1 to right on paths to leaves.

## Answer

Huffman's algorithm is greedy: repeatedly join the two lowest-weight trees until only one tree remains.

```text
HuffmanCode(symbols[1..n], freq[1..n])
1. For each symbol create a leaf node with its frequency
   and insert all leaves in a priority queue Q (min-heap on frequency).
2. For i = 1 to n-1:
      a. x = ExtractMin(Q)               (smallest weight)
      b. y = ExtractMin(Q)               (next smallest)
      c. create a new node z:
             z.left   = x
             z.right  = y
             z.weight = x.weight + y.weight
      d. Insert z into Q
3. The one node left in Q is the root of the Huffman tree.
4. Traverse the tree from the root: append 0 when going to the
   left child and 1 when going to the right child. The path to a
   leaf is the code of that symbol.
```

Pseudo-code for code assignment:

```text
Assign(node, code)
   if node is a leaf: code(node.symbol) = code
   else: Assign(node.left,  code + "0")
         Assign(node.right, code + "1")
```
Complexity: with a heap each insertion/extraction costs O(log n), and the loop performs about 3n of them (2(n − 1) extractions and n − 1 insertions), so the total is O(n log n). A sorted list gives O(n²).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does Huffman's algorithm do repeatedly?
   A. Joins the two highest-weight trees
   B. Splits the heaviest tree
   C. Sorts the symbols alphabetically
   D. Joins the two lowest-weight trees
   Answer: D. It is greedy: the two smallest weights are merged. (Key point: Greedy step)

2. How many merges are performed for n symbols?
   A. n
   B. n - 1
   C. n/2
   D. 2n
   Answer: B. Each merge reduces the number of trees by one, starting from n. (Key point: Iterations)

3. What weight does the new node get?
   A. The larger child's weight
   B. The average
   C. Zero
   D. The sum of its two children's weights
   Answer: D. z.weight = x.weight + y.weight. (Key point: New node)

4. What is the time complexity with a min-heap?
   A. O(n)
   B. O(n log n)
   C. O(n^2)
   D. O(log n)
   Answer: B. About 2n heap operations each costing O(log n). (Key point: Complexity)

## Related in Data Structure and Algorithm

- [Huffman tree definition and example](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahuffman-tree-properties) — Data Structure and Algorithm, chapter 6
- [Huffman encoding of symbols A to F](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahuffman-encode-symbols) — Data Structure and Algorithm, chapter 6

## Related in other subjects

- [Huffman code tree steps with example](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Ahuffman-code-tree-steps) — Multimedia System, chapter 5, asked 7×
- [Huffman code for a sentence (Kun Mandir)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-kun-mandir) — Data Communication, chapter 8
- [Huffman code for p = 0.6, 0.2, 0.1, 0.05, 0.05](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-p06-02-01) — Data Communication, chapter 8
- [Huffman code for five symbols (0.2, 0.35, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-five-symbols-02-035) — Data Communication, chapter 8