---
title: "Huffman encoding of symbols A to F"
subject: "Data Structure and Algorithm"
chapter: 6
key: "semester_4/data_structure_and_algorithm:huffman-encode-symbols"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/huffman-encode-symbols
site: BCT Engineering
---

# Huffman encoding of symbols A to F

Data Structure and Algorithm · Chapter 6: Trees

- Asked in: 2068 Bhadra, 6+2 marks
- Video: [Huffman Tree & Codes Example1 | Greedy Tech.| L 125 | Design & Analysis of Algorithm](https://www.youtube.com/watch?v=qPIyFx1fexs) — CSE Guru
- 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-encode-symbols
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6

## Question

Encode the symbols A, B, C, D, E and F with frequencies 0.10, 0.08, 0.15, 0.12, 0.30 and 0.25 respectively by using Huffman algorithm. Also calculate average number of bits used to encode a symbol.

## Short answer

Combine smallest frequencies stepwise: B(0.08)+A(0.10)=0.18, D(0.12)+C(0.15)=0.27, (BA)+F(0.25)=0.43, (DC)+E(0.30)=0.57, merge for root. Codes: A=001, B=000, C=101, D=100, E=11, F=01. Average bits = sum(freq × length) = 2.45 bits/symbol.

## Answer

Arrange the symbols by frequency: B 0.08, A 0.10, D 0.12, C 0.15, F 0.25, E 0.30. At each step join the two smallest weights; the smaller one is placed on the left (edge 0).

#### Construction
| Step | Two smallest | Merged weight | List after step |
|---|---|---|---|
| 1 | B 0.08 + A 0.10 | 0.18 | D 0.12, C 0.15, (BA) 0.18, F 0.25, E 0.30 |
| 2 | D 0.12 + C 0.15 | 0.27 | (BA) 0.18, F 0.25, (DC) 0.27, E 0.30 |
| 3 | (BA) 0.18 + F 0.25 | 0.43 | (DC) 0.27, E 0.30, (BAF) 0.43 |
| 4 | (DC) 0.27 + E 0.30 | 0.57 | (BAF) 0.43, (DCE) 0.57 |
| 5 | (BAF) 0.43 + (DCE) 0.57 | 1.00 | root |

#### Huffman tree
```text
                  1.00
               /        \
           0.43          0.57
          /    \        /    \
       0.18    F:0.25 0.27    E:0.30
       /  \            /  \
    B:.08 A:.10     D:.12 C:.15
```

#### Codes (left = 0, right = 1)
| Symbol | Frequency | Code | Length | Freq × length |
|---|---|---|---|---|
| A | 0.10 | 001 | 3 | 0.30 |
| B | 0.08 | 000 | 3 | 0.24 |
| C | 0.15 | 101 | 3 | 0.45 |
| D | 0.12 | 100 | 3 | 0.36 |
| E | 0.30 | 11 | 2 | 0.60 |
| F | 0.25 | 01 | 2 | 0.50 |

#### Average number of bits per symbol
L = Σ (frequency × code length) = 0.30 + 0.24 + 0.45 + 0.36 + 0.60 + 0.50 = 2.45

**Answer: 2.45 bits per symbol** (a fixed-length code would need 3 bits). The exact codes may differ if the left/right choice is reversed, but the average length is always 2.45.

## Check yourself

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

1. Which two symbols are merged first?
   A. E and F
   B. C and D
   C. B (0.08) and A (0.10)
   D. A and C
   Answer: C. They are the two smallest frequencies, forming 0.18. (Key point: First merge)

2. What is the next merge?
   A. D (0.12) + C (0.15) = 0.27
   B. F + E = 0.55
   C. BA + F = 0.43
   D. D + BA = 0.30
   Answer: A. After step 1, D and C are the two smallest weights in the list. (Key point: Second merge)

3. Which symbols get 2-bit codes?
   A. A and B
   B. C and D
   C. E and F
   D. Only E
   Answer: C. E (0.30) and F (0.25) sit at depth 2, while A, B, C and D are at depth 3. (Key point: Code lengths)

4. What is the average bits per symbol?
   A. 2.45
   B. 2.0
   C. 3.0
   D. 2.15
   Answer: A. 0.30+0.24+0.45+0.36+0.60+0.50 = 2.45. Swapping left/right does not change this. (Key point: Average)

## Related in Data Structure and Algorithm

- [Algorithm for Huffman code](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahuffman-code-algorithm) — Data Structure and Algorithm, chapter 6
- [AVL tree for 24, 12, 8, 15, 35, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-24-12-8) — Data Structure and Algorithm, chapter 6
- [AVL tree for 10, 20, 30, 35, 50, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30-35) — Data Structure and Algorithm, chapter 6
- [AVL tree for 10 20 30 50 45 40 8 5 3](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30) — Data Structure and Algorithm, chapter 6
- [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
- [Best, average, worst case of sorts](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Asorting-cases-big-oh) — Data Structure and Algorithm, chapter 7

## Related in other subjects

- [Source coding; Huffman for five symbols (0.3, 0.25, 0.2, 0.15, 0.1)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-huffman-five-s0) — Communication Systems, chapter 6
- [Symbol rate, entropy and information rate (6 symbols per 10 μs)](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asymbol-rate-six-symbols-10us) — Communication Systems, chapter 6
- [Importance of source coding; Huffman for eight symbols at 1000 symbols/s](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-coding-huffman-eight-1000) — Communication Systems, chapter 6
- [Huffman code for symbols A to E (0.4, 0.3, ...)](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-table-abcde) — Data Communication, chapter 8