--- title: "Huffman code tree steps with example" subject: "Multimedia System" chapter: 5 key: "semester_8/multimedia_system:huffman-code-tree-steps" source: https://www.bctengineer.com/q/semester_8/multimedia_system/huffman-code-tree-steps site: BCT Engineering --- # Huffman code tree steps with example Multimedia System · Chapter 5: Data Compression - Asked in: 2076 Bhadra, 10 marks; 2074 Magh, 10 marks; 2072 Magh, 4+10 marks; 2071 Bhadra, 10 marks; 2073 Bhadra, 8 marks; 2072 Asoj, 8 marks; 2075 Bhadra, 4 marks (asked 7 times) - Video: [Huffmans coding tree algorithm example - Multimedia Numericals](https://www.youtube.com/watch?v=eu-a12kBtc8) — Simple Snippets - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/multimedia_system/huffman-code-tree-steps - Whole chapter: https://www.bctengineer.com/md/semester_8/multimedia_system/chapter-5 ## Question Explain the Huffman coding algorithm: what are the steps to create the Huffman code tree? Explain with example. ## Short answer List symbols with probabilities, sort ascending, combine the two smallest into a parent node, repeat until one root remains, label branches 0 and 1, then read codes from root to leaf. For A=.4, B=.3, C=.15, D=.1, E=.05, codes are A=0, B=10, C=110, E=1110, D=1111, average 2.05 bits/symbol. ## Answer Huffman coding is a lossless, variable-length, entropy coding method. It gives short codes to frequent symbols and long codes to rare symbols, so the average code length is minimum. The codes are prefix codes: no code is the start of another, so decoding is unambiguous. #### Steps to build the Huffman code tree 1. List all symbols with their probabilities (or frequencies). 2. Sort them in ascending order of probability. 3. Take the two nodes with the smallest probabilities and join them under a new parent node whose probability is their sum. 4. Put the new node back in the list and sort again. 5. Repeat steps 3 and 4 until only one node (the root, probability 1) remains. 6. Label every left branch 0 and every right branch 1 (or the reverse, consistently). 7. Read the code of each symbol by following the path from the root to its leaf. #### Example Symbols and probabilities: A = 0.40, B = 0.30, C = 0.15, D = 0.10, E = 0.05. | Step | Combine | New node | |---|---|---| | 1 | E (0.05) + D (0.10) | ED = 0.15 | | 2 | C (0.15) + ED (0.15) | CED = 0.30 | | 3 | B (0.30) + CED (0.30) | BCED = 0.60 | | 4 | A (0.40) + BCED (0.60) | Root = 1.00 | ```text Root(1.0) 0/ \1 A(.4) BCED(.6) 0/ \1 B(.3) CED(.3) 0/ \1 C(.15) ED(.15) 0/ \1 E(.05) D(.10) ``` Codes read from the root: | Symbol | Probability | Code | Length | |---|---|---|---| | A | 0.40 | 0 | 1 | | B | 0.30 | 10 | 2 | | C | 0.15 | 110 | 3 | | E | 0.05 | 1110 | 4 | | D | 0.10 | 1111 | 4 | (Here the 0/1 labels on the last branch put E on 0 and D on 1; swapping them is equally valid.) **Average length** = 0.40(1) + 0.30(2) + 0.15(3) + 0.05(4) + 0.10(4) = 0.40 + 0.60 + 0.45 + 0.20 + 0.40 = **2.05 bits/symbol**. A fixed-length code for 5 symbols needs 3 bits, so Huffman saves (3 - 2.05)/3 = 31.7%. **Decoding example:** the bit string 0 10 110 0 decodes as A B C A, because no code is a prefix of another. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does Huffman coding assign to frequent and rare symbols? A. Long codes to frequent symbols, short to rare B. Equal-length codes to all symbols C. Short codes to frequent symbols and long codes to rare symbols D. Random codes to all symbols Answer: C. This minimises average code length. The codes are prefix codes, so decoding is unambiguous. (Key point: Basic idea) 2. In building the tree, which nodes are merged at each step? A. The two nodes with the largest probabilities B. The two nodes with the smallest probabilities, giving a parent whose probability is their sum C. The first and last nodes in the list D. Any two nodes chosen at random Answer: B. Repeatedly join the two smallest, re-sort, until one root with probability 1 remains. (Key point: Merging step) 3. For A=0.40 (code 0), B=0.30 (10), C=0.15 (110), D=0.10 (1111), E=0.05 (1110), what is the average length? A. 2.05 bits/symbol B. 2.50 bits/symbol C. 1.95 bits/symbol D. 3.00 bits/symbol Answer: A. 0.40 + 0.60 + 0.45 + 0.40 + 0.20 = 2.05 bits/symbol. (Key point: Average length) 4. Why can the bit string 0 10 110 0 be decoded without separators? A. Every code has the same length B. No code is a prefix of another code C. The decoder knows the probabilities of the message D. Codes are separated by zeros Answer: B. Prefix-free codes let the decoder read symbols unambiguously: here A B C A. (Key point: Prefix property) ## Related in Multimedia System - [Huffman code for symbols A to E](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Ahuffman-numerical-abcde) — Multimedia System, chapter 5 - [How Huffman code reduces file size](https://www.bctengineer.com/question.md?key=semester_8%2Fmultimedia_system%3Ahuffman-reduces-file-size) — Multimedia System, chapter 5 ## Related in other subjects - [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 - [Source vs channel coding; Huffman for five symbols](https://www.bctengineer.com/question.md?key=semester_6%2Fcommunication_systems%3Asource-channel-huffman-five) — 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 coding principle](https://www.bctengineer.com/question.md?key=semester_5%2Fdata_communication%3Ahuffman-principle) — Data Communication, chapter 8, asked 3×