--- title: "Huffman tree definition and example" subject: "Data Structure and Algorithm" chapter: 6 key: "semester_4/data_structure_and_algorithm:huffman-tree-properties" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/huffman-tree-properties site: BCT Engineering --- # Huffman tree definition and example Data Structure and Algorithm · Chapter 6: Trees - Asked in: 2072 Magh, 6 marks - Video: [L-4.3: Huffman Coding Algorithm in Hindi with Example | Greedy Techniques(Algorithm)](https://www.youtube.com/watch?v=uDS8AkTAcIU) — Gate Smashers - 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-tree-properties - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6 ## Question Define Huffman tree with its properties and example. ## Short answer A Huffman tree is a full binary tree that minimizes weighted external path length for optimal prefix codes. Build: repeatedly merge the two lowest-weight nodes; n leaves, n‑1 internal nodes. Example: merging A5,B9→14, C12,D13→25, 14+E16→30, 25+30→55, F45+55→100 gives codes F=0, C=100, D=101, A=1100, B=1101, E=111. ## Answer A **Huffman tree** is a binary tree built from a set of symbols with weights (frequencies), such that the weighted external path length Σ (weight × depth of leaf) is minimum. It is used to produce an optimal prefix code for lossless data compression: frequent symbols get short codes and rare symbols get long codes. #### Properties 1. It is a strictly (full) binary tree: every internal node has exactly two children. For n symbols there are n leaves and n − 1 internal nodes. 2. Each symbol is a leaf. An internal node holds the sum of the weights of its two children; the root weight is the total frequency. 3. Symbols of higher frequency are at a smaller depth (shorter code); the two least frequent symbols are siblings at the deepest level. 4. Labelling left edges 0 and right edges 1 gives a **prefix code**: no code is the prefix of another, so decoding is unambiguous. 5. The tree is not unique when weights tie, but all Huffman trees give the same minimum average code length. 6. Built greedily in O(n log n) with a min-heap. #### Example Symbols with frequencies: A = 5, B = 9, C = 12, D = 13, E = 16, F = 45. | Step | Merge | New weight | Remaining | |---|---|---|---| | 1 | A(5) + B(9) | 14 | C12, D13, 14, E16, F45 | | 2 | C(12) + D(13) | 25 | 14, E16, 25, F45 | | 3 | 14 + E(16) | 30 | 25, 30, F45 | | 4 | 25 + 30 | 55 | F45, 55 | | 5 | F(45) + 55 | 100 | root | ```text 100 / \ F:45 55 / \ 25 30 / \ / \ C:12 D:13 14 E:16 / \ A:5 B:9 ``` Codes (left = 0, right = 1): F = 0, C = 100, D = 101, A = 1100, B = 1101, E = 111. Average length = (45×1 + 12×3 + 13×3 + 5×4 + 9×4 + 16×3)/100 = 224/100 = 2.24 bits per symbol, against 3 bits for fixed-length codes. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does a Huffman tree minimize? A. The weighted external path length (sum of weight x leaf depth) B. The number of leaves C. The tree height only D. The number of internal nodes Answer: A. It gives an optimal prefix code. (Key point: Purpose) 2. For n symbols, how many internal nodes does it have? A. n B. n + 1 C. n - 1 D. 2n Answer: C. It is strictly binary with n leaves, so 2n - 1 total nodes. (Key point: Node count) 3. What is the benefit of labelling edges 0 and 1? A. No code is a prefix of another, so decoding is unambiguous B. All codes have equal length C. Codes are sorted D. Codes can be shorter than 1 bit Answer: A. Symbols are at leaves only, so no path to a leaf is the start of another. (Key point: Prefix code) 4. In the example, what is the average code length? A. 3 bits per symbol B. 2.45 bits per symbol C. 2.24 bits per symbol D. 1.5 bits per symbol Answer: C. Sum of freq x length = 224/100 = 2.24, less than 3 bits for fixed length. (Key point: Average length) ## Related in Data Structure and Algorithm - [B-tree properties; order 5 for 3, 14, 7, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-properties-order5-3-14) — Data Structure and Algorithm, chapter 6, asked 2× - [Spanning tree properties; Round Robin MST](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aspanning-tree-properties-round-robin) — Data Structure and Algorithm, chapter 10 - [BST properties and recursive search](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abst-properties-recursive-search) — Data Structure and Algorithm, chapter 6 - [MST definition; Kruskal's MST on 6-vertex graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Amst-definition-kruskal-graph-i) — Data Structure and Algorithm, chapter 10 ## 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× - [Define tree; properties and applications](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Atree-definition-properties-applications) — Discrete Structure, chapter 4 - [Flow net: definition, properties, uses](https://www.bctengineer.com/question.md?key=semester_4%2Fsoil_mechanics%3Aflow-net-properties-applications) — Soil Mechanics, chapter 7, asked 7× - [Standard normal: definition, properties, importance](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Astandard-normal-definition-properties-importance) — Probability and Statistics, chapter 3, asked 2×