How Huffman Coding Works and How to Read Its Tree
Learn how Huffman coding builds a tree from symbol frequencies, gives shorter codes to common symbols, and lets you decode a binary message step by step.
Huffman coding compresses data by giving shorter binary codes to symbols that occur more often. A Huffman tree shows how those codes are made and lets you decode them: start at the top and follow the branches to a symbol.
Building the tree
Count how often each symbol appears. Join the two symbols with the lowest frequencies, then label their new parent with their combined frequency. Repeat, each time joining the two lowest-frequency items, until everything is connected in one tree. An item might now be a single symbol or a group of symbols.
For example, suppose a message contains A four times, B twice, C once and D once. Join C and D to make a group with frequency 222. Join that group with B to make a group with frequency 444. Finally, join that group with A.
Reading the tree
Starting at the top (the root), label each left branch 000 and each right branch 111. The route from the root to a symbol gives its code. With A on the left and the other symbols on the right, one valid set of codes is A = 000, B = 101010, C = 110110110 and D = 111111111.
To decode 100110100110100110, start at the root. Follow 101010 to B, then return to the root. Follow 000 to A, return again, and follow 110110110 to C. The message is BAC.
Exam mistake to avoid: Do not read a bit as a complete symbol until you reach the end of a branch, called a leaf. Also, tied frequencies can produce different valid trees, so your codes may differ from someone else's while still decoding correctly.
