TAOCP 2.3.4.4 Exercise 16
The construction described after (16) already yields an efficient method.
Section 2.3.4.4: Enumeration of Trees
Exercise 16. [**] [25] Design an algorithm (as efficient as possible) that converts from the canonical representation of an oriented tree to a conventional computer representation using PARENT links.
Verified: no
Solve time: 1m11s
The construction described after (16) already yields an efficient method. Let $x_1,x_2,\ldots,x_{n-1}$ be the canonical representation. Compute, for each vertex $v$, the number $C[v]$ of occurrences of $v$ among $x_1,\ldots,x_{n-1}$. Maintain all vertices with $C[v]=0$ in an ordered set from which the smallest element can be extracted.
For $j=1,2,\ldots,n-1$, let $V_j$ be the smallest vertex with $C[V_j]=0$. Set
$$ \mathrm{PARENT}[V_j]\leftarrow x_j, $$
delete $V_j$ from further consideration, decrease $C[x_j]$ by $1$, and if $C[x_j]$ becomes $0$, insert $x_j$ into the ordered set. After the $(n-1)$st step, the unique remaining vertex is the root; set
$$ \mathrm{PARENT}[\text{root}]\leftarrow 0. $$
The algorithm performs exactly one assignment to a parent field for each of the $n$ vertices, hence exactly $n$ replacements of the form $\leftarrow$. Using a priority queue or equivalent ordered set, each insertion and deletion requires $O(\log n)$ time, so the entire conversion requires $O(n\log n)$ time and $O(n)$ memory. If the vertices are maintained in a linked structure indexed by label, the smallest zero-count vertex can be found and updated in constant amortized time, giving a linear-time implementation.