Skills101

AdvancedDiscrete Mathematics · Lesson 14 of 14 · Updated ·

Rooted Trees, Prefix Codes and Huffman Coding — m-ary Tree Formulas, Unique Decoding and Optimal Codes

The graph theory lesson defined a tree as a connected graph with no cycles. When we pick one vertex as the root and hang everything below it, we get a rooted tree — the shape of folders on your laptop, of a knockout tournament, and of the codes used to compress files. This lesson covers the counting formulas for m-ary trees and then uses binary trees to build prefix codes, ending with Huffman coding, a standard topic in discrete maths and in algorithms courses.

1. Rooted tree vocabulary

TermMeaning
rootthe chosen top vertex; it has no parent
parent / childif u is just above v on the path from the root, u is v's parent and v is u's child
leafa vertex with no children
internal vertexa vertex with at least one child
level of vnumber of edges from the root to v (the root is at level 0)
heightthe largest level of any vertex
m-ary treeevery internal vertex has at most m children (binary: m = 2, ternary: m = 3)
full m-ary treeevery internal vertex has exactly m children

2. Counting formulas for full m-ary trees

Let a full m-ary tree have n vertices, i internal vertices and l leaves. Every vertex except the root is the child of exactly one internal vertex, and each internal vertex has exactly m children. So:

n = m·i + 1

Every vertex is either internal or a leaf, so n = i + l. Putting the two together:

l = (m − 1)·i + 1 and i = (l − 1) / (m − 1)

Given any one of n, i, l (and m), you can find the other two.

A full ternary tree with a root, three internal children and nine leaves: 4 internal vertices, 13 vertices in total and 9 leaves, matching n = mi + 1 and l = (m − 1)i + 1

def grow_full_tree(m, internal):
    """Start with one leaf; each step turns the oldest leaf into an internal vertex with m children."""
    leaves, n = [0], 1
    for _ in range(internal):
        leaves.pop(0)
        leaves += list(range(n, n + m))
        n += m
    return n, len(leaves)

for m, i in [(2, 7), (3, 4), (4, 10)]:
    n, l = grow_full_tree(m, i)
    print(f"m={m}, i={i:2}: n={n:2} (mi+1={m * i + 1:2}), leaves={l:2} ((m-1)i+1={(m - 1) * i + 1:2})")

teams = 64
print("knockout with", teams, "teams:", teams - 1, "matches")   # full binary tree: i = l - 1
m=2, i= 7: n=15 (mi+1=15), leaves= 8 ((m-1)i+1= 8)
m=3, i= 4: n=13 (mi+1=13), leaves= 9 ((m-1)i+1= 9)
m=4, i=10: n=41 (mi+1=41), leaves=31 ((m-1)i+1=31)
knockout with 64 teams: 63 matches

Worked example (knockout tournament). In a knockout tournament each match has two teams and one winner. Draw it as a full binary tree: the teams are the leaves and each match is an internal vertex. With l = 64 leaves and m = 2, i = (64 − 1)/(2 − 1) = 63 matches. A quicker argument gives the same answer: every match knocks out exactly one team, and 63 teams must be knocked out.

Height bound. An m-ary tree of height h has at most mʰ leaves. So a tree with l leaves has height at least ⌈log_m l⌉. For example, any binary tree with 64 leaves has height at least 6. This is the same idea behind the lower bound for comparison sorting.

3. Prefix codes

Computers store characters as bit strings. A fixed-length code gives every character the same number of bits: 5 characters need 3 bits each (2² = 4 is too few). A variable-length code gives frequent characters short codes, which saves space. But then we must be able to tell where one code word ends.

A code is a prefix code when no code word is a prefix (beginning) of another. Then the bit string can be read from left to right without any separators: as soon as the bits read so far form a code word, that must be the character.

Every prefix code is a binary tree: characters sit at leaves, a left edge is 0, a right edge is 1, and the code of a character is the path from the root. Because characters are only at leaves, no path to one character passes through another, which is exactly the prefix property.

def is_prefix_free(code):
    words = list(code.values())
    return not any(a != b and b.startswith(a) for a in words for b in words)

def parses(bits, code):
    """All ways to split bits into code words (more than one = ambiguous)."""
    if not bits:
        return [""]
    out = []
    for ch, w in code.items():
        if bits.startswith(w):
            out += [ch + rest for rest in parses(bits[len(w):], code)]
    return out

huffman = {"a": "0", "c": "100", "d": "101", "b": "110", "r": "111"}
bad = {"a": "0", "b": "01", "c": "1"}

print("Huffman code prefix-free?", is_prefix_free(huffman))
print("  0110111 ->", parses("0110111", huffman))
print("bad code prefix-free?", is_prefix_free(bad))
print("  0101 ->", parses("0101", bad))
Huffman code prefix-free? True
  0110111 -> ['abr']
bad code prefix-free? False
  0101 -> ['acac', 'acb', 'bac', 'bb']

In the bad code, 0 (a) is a prefix of 01 (b), and the four bits 0101 can be read in four different ways. A prefix code always gives exactly one reading.

4. Huffman's algorithm

Which prefix code uses the fewest total bits for a given text? David Huffman's greedy algorithm (1952) finds one:

  1. Make each character a one-vertex tree, with weight = its frequency.
  2. Repeatedly take the two trees with the smallest weights and join them under a new root whose weight is their sum.
  3. Stop when one tree is left. Read the codes from it.

Example text: abracadabra, with frequencies a:5, b:2, r:2, c:1, d:1.

import heapq
from collections import Counter

text = "abracadabra"
freq = Counter(text)
print("frequencies:", dict(sorted(freq.items(), key=lambda kv: (-kv[1], kv[0]))))

# heap items: (weight, tie-break number, tree); a tree is a letter or a pair (left, right)
heap = [(w, i, ch) for i, (ch, w) in enumerate(sorted(freq.items()))]
heapq.heapify(heap)
count = len(heap)
while len(heap) > 1:
    w1, _, t1 = heapq.heappop(heap)          # the two lightest trees ...
    w2, _, t2 = heapq.heappop(heap)
    print(f"merge {w1} + {w2} = {w1 + w2}")
    heapq.heappush(heap, (w1 + w2, count, (t1, t2)))   # ... become one
    count += 1
tree = heap[0][2]

def codes(t, prefix=""):
    if isinstance(t, str):
        return {t: prefix or "0"}
    return {**codes(t[0], prefix + "0"), **codes(t[1], prefix + "1")}

code = codes(tree)
for ch in sorted(code, key=lambda c: (len(code[c]), c)):
    print(f"  {ch}: {code[ch]}")
bits = "".join(code[ch] for ch in text)
print("Huffman bits:", len(bits), "  fixed 3-bit code:", 3 * len(text))
frequencies: {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}
merge 1 + 1 = 2
merge 2 + 2 = 4
merge 2 + 4 = 6
merge 5 + 6 = 11
  a: 0
  b: 110
  c: 100
  d: 101
  r: 111
Huffman bits: 23   fixed 3-bit code: 33

Huffman tree for abracadabra: the root 11 has leaf a:5 on the 0 side and an internal vertex 6 on the 1 side; 6 splits into 2 (leaves c:1 and d:1) and 4 (leaves b:2 and r:2); the codes are a 0, c 100, d 101, b 110, r 111

Check the total by hand: 5 × 1 (a) + 2 × 3 (b) + 2 × 3 (r) + 1 × 3 (c) + 1 × 3 (d) = 5 + 6 + 6 + 3 + 3 = 23 bits, against 11 × 3 = 33 bits for a fixed-length code. The total is also the sum of all internal-vertex weights: 2 + 4 + 6 + 11 = 23. That second method is a fast way to check exam answers.

Ties. When two trees have equal weight, you may pick either. Different choices can give different codes (even different code lengths), but the total number of bits is always the same minimum.

Common mistakes

  • Using n = mi + 1 for a tree that is not full. The formulas need every internal vertex to have exactly m children.
  • Merging the two largest weights, or merging a new tree with the next character without checking which two weights are now smallest.
  • Forgetting to multiply code length by frequency when computing total bits.
  • Thinking any variable-length code can be decoded. Only prefix codes (or other uniquely decodable codes) can, and Huffman codes are always prefix codes.
  • Expecting one unique Huffman code. Ties allow several correct trees; the total cost is what must match.

Quick recap

  • Rooted tree terms: root, parent, child, leaf, internal vertex, level, height; m-ary and full m-ary.
  • Full m-ary tree: n = mi + 1, l = (m − 1)i + 1. Knockout with l teams needs l − 1 matches.
  • An m-ary tree of height h has at most mʰ leaves.
  • Prefix code: no code word is a prefix of another; it is a binary tree with characters at leaves.
  • Huffman: repeatedly merge the two lightest trees. Total bits = Σ frequency × code length = sum of internal weights.

Practice what you learned

📝 Quiz: Rooted Trees and Huffman Coding5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →