Decoding Prufer code

Given an $n$-vertex tree $T$ with vertex set $[n]$, Prufer algorithm maps $T$ to its Prufer code $f(T)$ by iteratively writing down the neighbor of the smallest leaf $x$ followed by removing $x$. The algorithm halts when two vertices are left.

The mapping is bijective between the trees and $[n]^{n-2}$, which proves Cayley's formula $n^{n-2}$ for the number of $n$-vertex trees with vertex set $[n]$.

My students came up with a different way of decoding any given Prufer code $a=(a_1,a_2,\dots,a_{n-2})\in[n]^{n-2}$ to tree $T$. Define $a_{n-1}=n$ and $a_0=n$. Start with a tree $T$ with a single vertex $n$. For $i=n-1,n-2,\dots,1$, add $x_i$ to $T$ adjacent to $a_i$. If $a_{i-1}\in V(T)$ then $x_i$ is the largest number missing in $T$. Otherwise $x_i=a_{i-1}$.

Based on the algorithm, we prove the existence and uniqueness of $T$ satisfying $f(T)=a$.

Proof

It suffices to show that $x_i$ is less than any other leaf $x_j$ after $x_i$ is added where $i<j$.

When $x_j$ is added, we have $a_{j-1}\in V(T)$ or else $x_j$ would soon be nonleaf. So $x_j$ is the largest number, including $x_i$, that were missing in $T$ when $x_j$ is added. Thus $x_i<x_j$.

For uniqueness, note that the only flexibility we have when decoding is to not choose as leaf the largest number missing in $T$ when $a_{i-1}\in V(T)$. Suppose we ever do so when adding $y_i<x_i$ where the largest was $x_i$. The next added leaf is $y_{i-1}<y_i$, so $y_{i-1}<y_i<x_i$. From now on, $T$ has at least two leaves less than $x_i$. Hence after $x_i$ is added it is not the smallest leaf of $T$, meaning that we do not have such flexibility.