Prüfer Code

A bijection between labelled trees on $n$ vertices and sequences of length $n-2$ over $\{1,\dots ,n\}$. It gives an immediate proof of Cayley’s formula and a clean way to sample or count trees with degree constraints.

Encoding

Repeat $n-2$ times: find the leaf with the smallest label, append its neighbour to the code, and delete the leaf.

    1 - 3 - 2      code: leaf 1 -> append 3
        |          then leaf 2 -> append 3   (or as the process dictates)
        4

Naive is $O(n^2)$; with a pointer that only ever moves forward it becomes $O(n)$:

vector<int> pruferEncode(int n, vector<int>& par) {   // tree rooted at n-1
    vector<int> deg(n, 1);
    for (int i = 0; i < n - 1; i++) deg[par[i]]++;
 
    vector<int> code;
    int ptr = 0;
    while (deg[ptr] != 1) ptr++;
    int leaf = ptr;
    for (int i = 0; i < n - 2; i++) {
        int nxt = par[leaf];
        code.push_back(nxt);
        if (--deg[nxt] == 1 && nxt < ptr) leaf = nxt;   // new small leaf appeared
        else { while (deg[++ptr] != 1); leaf = ptr; }
    }
    return code;
}

Decoding

Compute each vertex’s degree as (its count in the code) $+1$. Then repeatedly take the smallest-labelled vertex of degree 1, join it to the next code entry, and decrement both degrees. The two vertices left at the end are joined.

Consequences

Result	Why
Cayley’s formula: $n^{n-2}$ labelled trees on $n$ vertices	the code is an arbitrary sequence of length $n-2$ over $n$ symbols
Vertex $v$ appears $\mathrm{deg}(v)-1$ times in the code	it is removed from the tree only when it becomes a leaf
Trees with prescribed degrees $d_1..d_n$	multinomial $\left(\genfrac{}{}{0ex}{}{n-2}{d_1-1,\dots ,d_n-1}\right)$
Forests with $k$ trees and specified roots	$k{n}^{n-k-1}$ (generalised Cayley)
Spanning trees of $K_{m,n}$	$m^{n-1}{n}^{m-1}$
Labelled trees where vertex $v$ is a leaf	$(n-1{)}^{n-2}$

The degree fact is the workhorse: any question of the form “count labelled trees where vertex $i$ has degree constraint $C_i$” becomes a counting problem over sequences, which is usually a multinomial or a small DP.

Uniform random tree generation

Generate $n-2$ uniformly random labels and decode. This samples a labelled tree uniformly at random in $O(n)$ — far better than the “add random edges and check acyclicity” approach, which is biased and slow.

vector<int> randomTree(int n) {
    vector<int> code(n - 2);
    for (auto& x : code) x = rng() % n;
    return pruferDecode(n, code);
}

This is the standard way to generate tree test cases for stress testing.

Related counting results

• Matrix-Tree theorem — counts spanning trees of an arbitrary graph as a determinant. Prüfer handles only complete graphs, but does so bijectively and constructively.
• Wilson’s algorithm — samples a uniform random spanning tree of any graph via loop-erased random walks.
• Kirchhoff’s theorem — the undirected Matrix-Tree statement.

A caution

Prüfer codes apply to labelled trees. Counting unlabelled (isomorphism classes of) trees is a much harder problem with no closed form — the counts are OEIS A000055, computed by Pólya enumeration. Do not use $n^{n-2}$ when the problem says “shapes”.

See also: Combinatorics · Matrix-Tree Theorem · Tree Fundamentals