Prüfer sequence

The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm.

Both coding and decoding can be reduced to integer radix sorting and parallelized.

Initially, vertex 1 is the leaf with the smallest label, so it is removed first and 4 is put in the Prüfer sequence.

Vertex 4 is now a leaf and has the smallest label, so it is removed and we append 5 to the sequence.

For each node set its degree to the number of times it appears in the sequence plus 1.