Students should be familiar with the process of using a tree to represent…

The idea

A Huffman tree is a binary tree built from character frequencies so that frequent characters get short codes and rare ones get long codes. To build it, list each character with its frequency, then repeatedly take the two lowest-frequency items, join them under a new parent node whose frequency is their sum, and return that parent to the list. Repeat until one root remains. Label each left branch 0 and each right branch 1 (or the reverse, applied consistently). A character's code is the sequence of branch labels on the path from root to that character's leaf. Because every character sits at a leaf, no code is a prefix of another, so decoding is unambiguous.

What earns the marks

• Identifies that the two lowest-frequency nodes (or items) are combined first, and that the new parent's frequency is the sum of the two.
• Recognises that this merging repeats, with the new parent re-entering the list, until a single root node remains.
• States that branch labels (commonly 0 and 1) along the path from root to leaf give each character's code.
• Recognises that characters are stored at leaves, giving prefix-free codes and unambiguous decoding.
• Correctly reads a code or merged frequency from a supplied tree rather than guessing from character order.

Common mistakes and how to put them right

• Merging the two highest-frequency items first.

  Put it right: Is that Huffman always combines the two lowest-frequency items.

• Placing characters at internal nodes.

  Put it right: Is that characters belong at leaf nodes, with internal nodes carrying summed frequencies.

• Reading a code from leaf to root or mixing branch labels.

  Put it right: Is to read consistently from root to leaf using one agreed 0/1 convention.

Exam tips

• Before answering, redraw or annotate the tree and mark each node's frequency so the merge order is visible.
• Check a candidate code by tracing the full root-to-leaf path and confirming no other character's code is a prefix of it.
• For 'next merge' questions, list current node frequencies in order and pick the two smallest, including any newly created parent.