Prüfer Sequence, in depth: the smallest-leaf encoding, linear-time encode and decode, Cayley's formula, degree-constrained counting and uniform random labelled trees

Encoding: remove the smallest leaf

Encoding uses one rule, applied n-2 times: find the leaf with the smallest label, write down the label of its only neighbour, and delete the leaf. When two vertices remain, stop; they are joined by the last edge, which the sequence does not need to store.

Take the tree on vertices 1..8 with edges 1-4, 2-4, 3-4, 4-5, 5-6, 6-7, 6-8. Its leaves are 1, 2, 3, 7 and 8. Step one removes leaf 1 and writes 4. Then leaf 2 goes (write 4), then leaf 3 (write 4). Vertex 4 now has a single neighbour, 5, so it is a leaf and the smallest one: remove it and write 5. Vertex 5 becomes a leaf next; removing it writes 6. Finally leaf 7 goes and writes 6, leaving 6 and 8. The sequence is (4, 4, 4, 5, 6, 6).

Two facts are visible already, and they power everything else. First, every vertex appears in the sequence exactly deg(v)-1 times: each time a neighbour is removed the vertex is written once, and it is written for all its neighbours but the last one, which either removes it or survives with it to the end. Leaves therefore never appear. Second, the largest label n is never removed, because a tree with at least two vertices has at least two leaves and n is never the smallest of them; the final edge always touches n.

Decoding, and why it is a bijection

Decoding reverses the process using the degree fact. Set deg(v) = 1 plus the number of times v occurs in the sequence. At each step the vertices with degree 1 are exactly the current leaves, so the smallest of them is the leaf the encoder removed at that step, and the sequence entry is its neighbour. Join them, decrement the neighbour's degree, mark the leaf used, and continue. After n-2 steps exactly two vertices still have degree 1; join them.

Run it on (4, 4, 4, 5, 6, 6). Initial degrees are 4 for vertex 4, 3 for 6, 2 for 5 and 1 for everyone else. The smallest degree-1 vertex is 1: join 1-4, vertex 4 drops to 3. Then 2-4 and 3-4, leaving vertex 4 at degree 1. The smallest degree-1 vertex is now 4 itself, paired with the next entry 5: join 4-5. Then 5-6, then 7-6, and the last two degree-1 vertices, 6 and 8, form the final edge. That is the original tree.

Because the decoder succeeds on any sequence of length n-2 whose entries lie in 1..n, and the encoder and decoder undo each other, the map is a bijection between trees and n^n-2 sequences. That is the whole proof of Cayley's formula.

Linear-time encode and decode

The direct implementation finds the smallest leaf with a heap and runs in O(n log n), which is fine for most uses. The classic linear-time version replaces the heap with a pointer that only moves forward. The key observation: when removing a leaf turns its neighbour into a leaf, that neighbour is the next leaf to remove if and only if its label is smaller than the pointer; otherwise the next leaf is found by advancing the pointer, which never has to move back. The pointer travels at most n positions in total, so both directions are O(n).

def prufer_encode(n, edges):
    """Tree on labels 0..n-1 (n >= 2) -> list of n-2 labels. O(n)."""
    if n < 2 or len(edges) != n - 1:
        raise ValueError("need a tree with n >= 2 vertices and n-1 edges")
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-1] * n                       # root at n-1, which is never removed
    stack, seen = [n - 1], [False] * n
    seen[n - 1] = True
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if not seen[v]:
                seen[v], parent[v] = True, u
                stack.append(v)
    if not all(seen):
        raise ValueError("edges do not form a connected tree")
    degree = [len(a) for a in adj]
    ptr = 0
    while degree[ptr] != 1:
        ptr += 1
    leaf, code = ptr, []
    for _ in range(n - 2):
        nxt = parent[leaf]
        code.append(nxt)
        degree[nxt] -= 1
        if degree[nxt] == 1 and nxt < ptr:  # neighbour just became the smallest leaf
            leaf = nxt
        else:
            ptr += 1
            while degree[ptr] != 1:
                ptr += 1
            leaf = ptr
    return code

def prufer_decode(code):
    """List of n-2 labels in 0..n-1 -> list of n-1 edges. O(n)."""
    n = len(code) + 2
    if any(not 0 <= v < n for v in code):
        raise ValueError("label out of range")
    degree = [1] * n
    for v in code:
        degree[v] += 1
    ptr = 0
    while degree[ptr] != 1:
        ptr += 1
    leaf, edges = ptr, []
    for v in code:
        edges.append((leaf, v))
        degree[v] -= 1
        if degree[v] == 1 and v < ptr:
            leaf = v
        else:
            ptr += 1
            while degree[ptr] != 1:
                ptr += 1
            leaf = ptr
    edges.append((leaf, n - 1))
    return edges

The code uses labels 0..n-1, the usual convention in programs; the worked example used 1..n, the usual convention in maths. Subtract one to feed the example in: prufer_encode(8, [(0,3),(1,3),(2,3),(3,4),(4,5),(5,6),(5,7)]) returns [3, 3, 3, 4, 5, 5], which is the worked sequence shifted down by one. Rooting at n-1 is safe because that vertex is never removed. Edge cases worth a test each: n = 2 gives an empty sequence and decodes to the single edge (0, 1); n = 1 has no Prüfer sequence at all and must be handled by the caller; duplicate or self-loop edges, and edge lists that are not connected, must be rejected by the encoder rather than silently encoded.

Counting with sequences

The degree fact turns counting problems into counting sequences. A tree in which vertex i has degree d_i corresponds to a sequence in which i appears exactly d_i-1 times, and the number of such sequences is the multinomial coefficient (n-2)! / ∏(d_i-1)!. For the worked tree, the degree pattern (1,1,1,4,2,3,1,1) allows 6!/(3!·1!·2!) = 60 labelled trees.

Other results follow the same way. The number of labelled trees in which a given vertex is a leaf is (n-1)^n-2, since that label simply never appears in the sequence. In a uniformly random labelled tree, a given vertex's degree minus one is binomial with n-2 trials and probability 1/n, so for large n degrees are approximately one plus a Poisson(1) variable: about 1/e of the vertices are leaves. For counting spanning trees of an arbitrary graph rather than the complete graph, use the matrix-tree theorem; Prüfer only speaks about the complete graph.

Uniform random labelled trees

Because the bijection is exact, drawing n-2 labels independently and uniformly and decoding them yields a uniformly random labelled tree in O(n) time, with no rejection and no bias:

import random

def random_labelled_tree(n, rng=random):
    """Uniform over all n**(n-2) labelled trees on 0..n-1."""
    if n == 1:
        return []
    return prufer_decode([rng.randrange(n) for _ in range(n - 2)])

That is the right generator for fuzzing tree algorithms, generating test inputs for LCA, centroid decomposition or tree DP code, and producing random networks for simulation. Know what the distribution looks like before relying on it: uniform labelled trees are bushy, with height on the order of the square root of n and many leaves, so they rarely produce the long paths or deep chains that trigger stack overflows and worst-case bounds. Add paths, stars and caterpillars to a test suite explicitly. Uniform over labelled trees is also not uniform over tree shapes, because symmetric shapes have fewer distinct labellings. To sample a uniform spanning tree of a specific graph rather than the complete graph, use Wilson's algorithm, covered in the random spanning tree article.

Failure modes and misuses

• Off-by-one labels. Mixing 1-based maths and 0-based code makes the decoder index past the end or silently produce a different tree. Convert at the boundary and test with n = 2 and n = 3.
• Trusting decoder input. Every in-range sequence is valid, but a label equal to n or a sequence of the wrong length is not. Validate length and range before decoding untrusted data.
• Encoding a non-tree. A cycle or a disconnected edge list will be encoded into something by a careless encoder and decoded into a different graph. Check n-1 edges and connectivity first.
• Expecting compression. A Prüfer sequence stores n-2 labels; a parent array stores n-1. The saving is one label. Use it for its bijection, not for its size.
• Using it as a genome. In evolutionary search, changing one sequence entry can change many edges of the decoded tree, so offspring barely resemble parents. Gottlieb, Julstrom, Raidl and Rothlauf (GECCO 2001) showed this poor locality makes Prüfer numbers a weak representation for spanning-tree search; edge-set encodings behave better.
• Unlabelled questions. Prüfer counts labelled trees. To count or deduplicate tree shapes, canonicalise with AHU tree isomorphism instead.

Testing an implementation exhaustively

The bijection makes the implementation unusually easy to test completely for small n. For each n from 2 to 7, enumerate every one of the n^n-2 sequences, decode each, check that the result has n-1 edges and is connected (a union-find pass does both), encode it again and require the original sequence back, and check that the decoded edge sets are all distinct. That covers 16,807 trees at n = 7 in well under a second, and it catches every pointer bug in the linear-time loops. Add a property test with random sequences for large n, and a test that encoding rejects cycles and forests.

Trade-offs against other tree representations

What to do next

1. Encode the worked tree by hand, then decode the sequence back without looking.
2. Implement both linear-time routines and the exhaustive n = 2..7 round-trip test.
3. Use the random generator to fuzz one of your own tree algorithms against a brute-force reference, and add paths and stars explicitly.
4. Count degree-constrained trees with the multinomial and verify it by enumeration for n = 6.
5. If you were planning to use Prüfer codes as a search representation, benchmark an edge-set encoding first.