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

Source: https://skills101.in/learn/discrete-math/dm-rooted-trees-prefix-codes-huffman — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-21.

The [graph theory lesson](https://skills101.in/learn/discrete-math/graph-theory-basics) 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

| Term | Meaning |
|---|---|
| **root** | the chosen top vertex; it has no parent |
| **parent / child** | if u is just above v on the path from the root, u is v's parent and v is u's child |
| **leaf** | a vertex with no children |
| **internal vertex** | a vertex with at least one child |
| **level** of v | number of edges from the root to v (the root is at level 0) |
| **height** | the largest level of any vertex |
| **m-ary tree** | every internal vertex has at most m children (binary: m = 2, ternary: m = 3) |
| **full m-ary tree** | every 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](https://skills101.in/learn-img/discrete-math/full-ternary-tree.svg)

```python
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
```

```text
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.

```python
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))
```

```text
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.

```python
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))
```

```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](https://skills101.in/learn-img/discrete-math/huffman-tree.svg)

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 quiz and free certificate: https://skills101.in/learn/discrete-math/dm-rooted-trees-prefix-codes-huffman