Finding the Tree for Prufer Code

Question

This is more of a fun question that I came up with. How would you go about building the tree for the prufer code:

$P(t) = 122333444455555666666777777788888888999999999(10)(10)(10)(10)(10)(10)(10)(10)(10)(10)$

Answer 1

I would take the easy way out and use Wolfram Alpha:

ResourceFunction["PruferCodeToLabeledTree"][{1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10}]

Resulting in

Answer 2

We can do this by hand, too.

First, we should determine what the vertices $1, 2, \dots, 10$ are doing. The idea is that when we generate the Prüfer code, one entry at a time, we are simultaneously deleting leaves of the tree, one leaf at a time (and recording the parent of the deleted leaf). So vertex $1$ becomes a leaf after the last "$1$" entry in the Prüfer code: it is the lowest label leaf, so it immediately gets deleted, and the very next entry of the code tells us $1$ is adjacent to $2$. Similar reasoning tells us that $2$ is adjacent to $3$, $3$ to $4$ and so on. So vertices $1, 2, \dots, 10$ form a path.

All other vertices in the tree must be leaves. They are filled in to make sure that vertices $1, 2, \dots, 10$ have degrees $2, 3, \dots, 11$ respectively: one more than the number of times they appear in the Prüfer code. We add them as leaves on the vertices $1, 2, \dots, 10$ in the order that they appear in the Prüfer code: $11$ is adjacent to $1$, $12$ is adjacent to $2$, $13$ and $14$ are adjacent to $3$, $15$ through $17$ are adjacent to $4$, and so on.