Construct the tree from the Prüfer code $(5,7,2,2,3,4)$

Key concept: Going from a Prüfer sequence back to a tree is the reverse of the leaf-removal process. The only thing that matters is staying faithful to the algorithm, especially the order in which edges are created.

Step by step

For the Prüfer code

$(5,7,2,2,3,4),$

the corresponding tree has $8$ vertices, because a Prüfer code of length $6$ comes from a tree on $6+2=8$ vertices.

Using the standard reconstruction algorithm, each step connects the smallest available leaf to the next code entry. The edges are added in this order:

$[1,5],\ [5,7],\ [6,2],\ [7,2],\ [2,3],\ [3,4],\ [4,8].$

So the tree can be described by that edge list.

Pitfall alert

Two classic mistakes show up here: first, forgetting that the tree has $n=|P|+2$ vertices; second, choosing a leaf that is not the smallest available label. That changes the whole tree.

Try different conditions

If the code had repeated numbers in a different pattern, the reconstruction still works the same way. Only the sequence changes; the algorithm does not. If one label were missing from the code entirely, that vertex would usually appear as a leaf in the final tree.

Further reading

Prüfer reconstruction, labeled tree, smallest available leaf