Merge a prefix-code tree
Build a variable-length prefix code by merging low weights and distinguish code length from symbol frequency.
Adult planning suggestion: about 9–12 · Logic & rule checking · Language & storytelling · Shape & spatial thinking
- Players
- Groups of 3
- Time
- 15–20 minutes
- Materials and quantities
- Four weighted symbol cards, three merge-node cards, a tree mat and encoding log per trio.
Thirty pupils: ten trios; merger, edge writer and decoder rotate after a merge.
Prepare
Use weights A=5, B=2, C=1 and D=1, representing the nine-symbol message AAAAABBCD. Each card begins as a separate tree. Repeated values are allowed; a weight is a frequency, not a bit. Use the rule of combining the two lowest current weights. For reproducible ties, compare the alphabetical strings of leaf names, place the smaller label on the left and name a merged node by all its leaf names sorted alphabetically.
Play
Join the selected trees under a new parent whose weight is their sum. Put 0 on its left edge and 1 on its right edge. Return this merged tree to the pool and repeat until one tree contains all four symbols. The code for a symbol is its root-to-leaf edge sequence. Do not label an internal node as a finished symbol: that could make one code a prefix of another and spoil direct decoding.
Worked example
Merge C1 with D1 to make CD2; merge B2 with CD2 to make BCD4; merge BCD4 with A5 to make ABCD9. With the stated ordering, A=1, B=00, C=010 and D=011. The weighted cost is 5×1 + 2×2 + 1×3 + 1×3 = 15 bits. A fixed two-bit code for nine symbols uses 18 bits. Count the weights, not just the four different letters.
Finish and check
Encode AAAAABBCD and decode it back to the same nine symbols. The checked bit sequence is 111110000010011. Stop after the tree, codes and round trip agree, or after twenty minutes with the partial tree preserved. Another tie convention may change the exact bit strings without changing the code lengths here; accept a correctly built tree and round trip if that convention was clearly stated before construction.
Adaptation and practical limits
Thirty pupils: ten trios as merger, edge labeller and decoder, swapping roles after each merge. Adult planning suggestion is about 9–12 with multiplication help. The university source explains data compression, not tested classroom gains. This is a public symbolic code, not encryption. Paper cards can be drawn by hand, and the node weights should remain visible while checking each sum.
Aim: Build a variable-length prefix code by merging low weights and distinguish code length from symbol frequency.
Practice within this activity: Preserve the two-smallest rule and calculate a frequency-weighted cost.
Adult observation: Ask why an internal node cannot also be a symbol code; do not score writing speed.
Mechanism and adaptation: Our version uses Huffman-style weighted binary-tree construction. Examples and sheets are separately written; the earliest inventor is not established here.
Reference checked 25 October 2026: Princeton Algorithms · Data Compression — Technical background for prefix-free and Huffman codes; our four weights, tie convention and message are separately prepared, not encryption.
Goals describe observable activity choices, not measured long-term gains or institutional endorsement.
Free alternatives: Use paper or clean reused cardboard and a pencil. Copy the supplied diagrams and tables by hand; no specialist kit or purchase is needed.
Printable materials
Preview at 100% scale, with browser headers and footers off. Cut with suitable help. Keep host keys separate. This is a manual tabletop kit, not an online opponent, automatic judge or solver.
Player weighted leaves and merge blanks
Repeatedly merge the two lowest weights. Tie by alphabetical sorted leaf labels. Left0, right1.
Player tree and encoding log
| Merge | Two current weights | Sum / label |
|---|---|---|
| ________ | ________ | ________ |
| ________ | ________ | ________ |
| ________ | ________ | ________ |
| Symbol | Code | Weight×length |
|---|---|---|
| A | ________ | ________ |
| B | ________ | ________ |
| C | ________ | ________ |
| D | ________ | ________ |
Message AAAAABBCD. Encode: ____________________. Decode back: ____________________.
Host / teacher checked example · separate
Thirty pupils: ten trios; merger, edge writer and decoder rotate after a merge.
Four weighted symbol cards, three merge-node cards, a tree mat and encoding log per trio.
Keep this answer page separate. Read the full web rules and preview materials before leading; allow pauses, passing and supported writing.
| Merge | Result |
|---|---|
| 1 | C1 + D1 → CD2 |
| 2 | B2 + CD2 → BCD4 |
| 3 | BCD4 + A5 → ABCD9 |
| Symbol | Code | Weighted bits |
|---|---|---|
| A | 1 | 5 |
| B | 00 | 4 |
| C | 010 | 3 |
| D | 011 | 3 |
AAAAABBCD →111110000010011 (15bits), versus18 fixed-length bits. No codeword prefixes another.
A fresh three-symbol frequency check · separate player exercise
| Symbol | Weight | Code | Weighted length |
|---|---|---|---|
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
Encode AAAAAABBBC and then decode it.
A fresh three-symbol frequency check · host check
Merge C1+B3→BC4, then BC4+A6→10. Codes A1,B01,C00. Weighted length6×1+3×2+1×2=14, compared with20 for fixed two-bit coding. Encoded message11111101010100 has14 bits and decodes to the same ten symbols.
Related activities
A fresh three-symbol frequency check
Use new weights A6,B3,C1 on a separate tree. Keep the original four-symbol tree intact. Merge the two lightest current trees, assigning0 to the lower-weight child and1 to the other; no tie occurs in this new instance.