AQA · GCSE · Computer Science
Course version: 8525 · Version from Sept 2020
Data compression: Be able to interpret Huffman trees.
Interpreting a Huffman tree means reading information from a diagram you are given.
Checked against the AQA 8525 specification (opens in a new tab) on .
- Point 6 of 13
Study notes
From the checked teaching notes for this specification point.
The idea
Interpreting a Huffman tree means reading information from a diagram you are given. Trace from the root along labelled branches (typically 0 for left, 1 for right) to reach a character's leaf; the labels on that path form its code. The frequency at any internal node equals the sum of the frequencies below it, and the root frequency equals the total of all character frequencies. Shorter paths correspond to more frequent characters, which is why Huffman coding compresses well. To decode a bit string, start at the root and follow each bit until you reach a leaf, output that character, then restart at the root for the next bits. Because no code is a prefix of another, decoding never needs a separator.
What earns the marks
- Traces a root-to-leaf path using the branch labels to state a character's code correctly.
- States that an internal node's frequency is the sum of the frequencies of the nodes beneath it, and the root gives the total.
- Recognises that characters with shorter paths are more frequent, giving compression.
- Decodes a bit string by following bits from the root to a leaf, outputting the character, then restarting at the root.
- Explains that prefix-free leaf codes allow unambiguous decoding without separators.
Common mistakes and how to put them right
Reading codes from leaf to root.
Put it right: Is to always start at the root and follow branches downward to the leaf.
Assuming a fixed-length code.
Put it right: Is that Huffman codes vary in length according to frequency.
Decoding a whole string in one pass without restarting at the root after each character.
Put it right: Is to return to the root after outputting each leaf character.
Exam tips
- Annotate each branch with its 0/1 label before tracing any code so you do not lose your place.
- For decoding, mark each bit as you consume it and write the output character only when you reach a leaf.
- Verify a decoded string by re-encoding it and checking it matches the original bit string.
Try the lesson
The start of the Data compression: Be able to interpret Huffman trees. lesson, made from checked teaching notes for this specification point.
Have a go first
In a Huffman tree, the character 'E' is reached by following the branch labelled 0 from the root. How many bits does the code for 'E' contain?
There is more to this lesson
The full lesson goes on to check your understanding and help you earn the marks. Create a free account to carry on, with your progress saved.
A week of Premium from your first lesson · Then the free plan continues · No card, no charge
Test your understanding of Data compression: Be able to interpret Huffman trees.
Active recall beats re-reading. Take an instant quiz now to test what you’ve learned and lock it into long-term memory.
A week of Premium from your first lesson · Then the free plan continues · No card, no charge