Decoding Prüfer Sequences Into Trees

From a Sequence to a Labeled Tree

A Prüfer sequence records information about a labeled tree in a compact list. Decoding reverses the direction of the task: given the list and its label set, construct the tree’s edges. The key is to keep track of two things at once: the labels still available as vertices, and the entries still present in the sequence. At each step, the least available label that does not occur in the remaining sequence becomes a leaf. Join it to the first entry of that sequence, then remove the leaf label and that first entry.

Throughout, labels come from a finite ordered set \(L\) of \(n\geq 1\) distinct labels. In the usual convention \(L=\{1,2,\dots,n\}\), so “least” refers to the usual order on integers. A sequence for this procedure has length \(n-2\), with every entry in \(L\), when \(n\geq2\). Repetitions are allowed. The sequence of length zero is used when \(n=1\) or \(n=2\), with the two cases producing different trees.

Here “absent” means that the label does not occur anywhere in the remaining sequence. The edge list is built as the procedure runs; active labels are the vertices not yet selected as leaves. The sequence entry used as the other endpoint is always its first entry, not an arbitrary occurrence or the last entry.

The Decoding Procedure

The updates must be synchronized: each step removes one active label and one sequence entry. If there are \(r\) active labels before a step, there are \(r-2\) entries in the remaining sequence. This length relationship explains both why an absent label is available and why the procedure stops with two labels and an empty sequence.

Why the Procedure Always Works

Proof. First consider \(n=1\). The procedure returns one vertex and no edges, which is connected and has no cycle, so it is a tree. Now suppose \(n\geq2\). Before any iterative step, there are \(n\) active labels and \(n-2\) sequence entries. Whenever a step is performed, one active label and one sequence entry are removed. Therefore, if there are \(r\) active labels, the remaining sequence has length \(r-2\).

Suppose \(r>2\). The sequence is nonempty, so its first entry exists. Every remaining sequence entry is an active label: this holds initially because all entries lie in \(L\), and the chosen label \(x\) is absent from the remaining sequence, so removing \(x\) cannot remove a label that occurs in it. There are at most \(r-2\) distinct labels appearing in a sequence of length \(r-2\). Thus at least \(r-(r-2)=2\) active labels are absent from it. A least such label \(x\) exists because the active set is finite and ordered. If \(y\) is the first entry, then \(y\) is active and \(y\neq x\), since \(x\) is absent. So the edge \(xy\) can be added without a loop. Each step reduces \(r\) by one, and after \(n-2\) steps exactly two active labels remain; the sequence then has length zero, so the final edge is well-defined.

It remains to show that the output is a tree. At the end, the last two active labels form a tree consisting of one edge. Now read the earlier steps in reverse order. At each reversed step, restore the label \(x\) that was removed and its edge \(xy\). When that edge was originally added, \(y\) was active; hence \(y\) was either one of the final two labels or a label removed at a later step. In reverse order, all such later-removed labels have already been restored. Therefore \(y\) is already in the graph when \(x\) is restored. Adding a new vertex with exactly one edge to an existing tree preserves connectedness and creates no cycle: any route from the new vertex must use its only incident edge, so a cycle through it cannot occur. Repeating this argument restores every label and preserves the tree property. No edge is a loop, and each added edge has a newly restored endpoint, so no edge is repeated. The resulting graph is simple and is a tree on \(L\). \(\square\)

Small Cases and Common Mistakes

Common mistake: use the original sequence to test absence. The test must use the sequence that remains after earlier entries have been deleted. For \((4,4,2,5)\), after the first step the active labels are \(\{2,3,4,5,6\}\) and the remaining sequence is \((4,2,5)\). Label \(3\) is the least active label absent from that current sequence, so the next edge is \(34\). After that step, the active labels are \(\{2,4,5,6\}\) and the sequence is \((2,5)\); now \(4\) is the least absent label, so the edge is \(42\). Using a stale absence list can instead select \(6\), which is absent but not the least currently absent label. The correction is to recompute absence at every step.

Common mistake: remove the wrong sequence entry. After selecting a leaf label, delete the first entry of the remaining sequence, because that is the label joined to the leaf. Do not delete an entry that happens to equal the leaf label: the leaf was selected precisely because it does not occur in the remaining sequence. For instance, the first step for \((4,4,2,5)\) adds \(14\) and leaves \((4,2,5)\), not \((4,2,5)\) after deleting a \(1\) (there was no \(1\) in the sequence to delete); the deleted entry is the first \(4\).

The decoder is useful because it makes a tree concrete: it turns a short list into an explicit vertex and edge set by a finite sequence of local decisions. Keeping the active labels and remaining sequence visible prevents most errors. The main checks are simple: the sequence length decreases by one at each leaf step, the active-label count decreases at the same time, and the final two active labels must be joined.