TAOCP 2.3.2 Exercise 18
Let the nodes be numbered $1,2,\ldots,n$ in their location order.
Section 2.3.2: Binary Tree Representation of Trees
Exercise 18. [25] An oriented tree specified by n links PARENT[j] for 1 <= j <= n implicitly defines an ordered tree if the nodes in each family are ordered by their location. Design an efficient algorithm that constructs a doubly linked circular list containing the nodes of this ordered tree in preorder. For example, given
$$ \begin{aligned} j &= 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8,\ \operatorname{PARENT}[j] &= 3\ 8\ 4\ 0\ 4\ 8\ 3\ 4, \end{aligned} $$
your algorithm should produce
$$ \begin{aligned} \operatorname{LLINK}[j] &= 3\ 8\ 4\ 6\ 7\ 2\ 1\ 5,\ \operatorname{RLINK}[j] &= 7\ 6\ 1\ 3\ 8\ 4\ 5\ 2, \end{aligned} $$
and it should also report that the root node is 4.
Verified: yes
Solve time: 57s
Solution
Let the nodes be numbered $1,2,\ldots,n$ in their location order. Since the children in each family are ordered by location, the preorder sequence is determined entirely by the array $\operatorname{PARENT}[j]$.
The construction can be done in linear time by first forming, for each node, the ordered list of its children, and then linking the nodes in preorder.
For each node $i$, maintain
$$ \operatorname{FIRST}[i],\qquad \operatorname{LAST}[i], $$
initially zero. Also let $\operatorname{ROOT}$ denote the unique node whose parent is $0$.
Process the nodes in increasing order of location:
$$ j=1,2,\ldots,n. $$
If $\operatorname{PARENT}[j]=0$, set $\operatorname{ROOT}\leftarrow j$.
Otherwise let
$$ p\leftarrow \operatorname{PARENT}[j]. $$
If $\operatorname{FIRST}[p]=0$, set
$$ \operatorname{FIRST}[p]\leftarrow j,\qquad \operatorname{LAST}[p]\leftarrow j. $$
Otherwise append $j$ to the end of the child list of $p$:
$$ \operatorname{RLINK}[\operatorname{LAST}[p]]\leftarrow j, \qquad \operatorname{LAST}[p]\leftarrow j. $$
After this pass, for every node $p$, the chain
$$ \operatorname{FIRST}[p] \to \operatorname{RLINK}[\operatorname{FIRST}[p]] \to \cdots $$
contains exactly the children of $p$ in location order.
Now construct the preorder list. Let $\operatorname{PREV}$ be the most recently visited node.
Define a recursive procedure $\operatorname{VISIT}(p)$:
$$ \begin{aligned} &\text{if }\operatorname{PREV}\ne0\text{ then}\ &\qquad \operatorname{RLINK}[\operatorname{PREV}] \leftarrow p,\ &\qquad \operatorname{LLINK}[p] \leftarrow \operatorname{PREV};\ &\text{else}\ &\qquad \operatorname{HEAD}\leftarrow p;\[2mm] &\operatorname{PREV}\leftarrow p;\[2mm] &c\leftarrow \operatorname{FIRST}[p];\ &\text{while }c\ne0\text{ do}\ &\qquad \operatorname{VISIT}(c),\ &\qquad c\leftarrow \operatorname{RLINK}[c]. \end{aligned} $$
Initialize
$$ \operatorname{PREV}\leftarrow0, $$
and execute
$$ \operatorname{VISIT}(\operatorname{ROOT}). $$
When the traversal is complete, the nodes are linked in preorder. To make the list circular, perform
$$ \operatorname{RLINK}[\operatorname{PREV}] \leftarrow \operatorname{HEAD}, \qquad \operatorname{LLINK}[\operatorname{HEAD}] \leftarrow \operatorname{PREV}. $$
The algorithm is linear. The first pass examines each node once. During the preorder traversal each node is visited once and each child link is followed once. Hence the total running time is $\Theta(n)$.
For the given example,
$$ \begin{aligned} j &=1\ 2\ 3\ 4\ 5\ 6\ 7\ 8,\ \operatorname{PARENT}[j] &=3\ 8\ 4\ 0\ 4\ 8\ 3\ 4. \end{aligned} $$
The root is
$$ \operatorname{ROOT}=4. $$
The ordered child lists are
$$ 4:(3,5,8),\qquad 3:(1,7),\qquad 8:(2,6). $$
Therefore the preorder sequence is
$$ 4,\ 3,\ 1,\ 7,\ 5,\ 8,\ 2,\ 6. $$
The circular predecessor and successor links are consequently
$$ \begin{aligned} \operatorname{LLINK}[4]&=6, & \operatorname{RLINK}[4]&=3,\ \operatorname{LLINK}[3]&=4, & \operatorname{RLINK}[3]&=1,\ \operatorname{LLINK}[1]&=3, & \operatorname{RLINK}[1]&=7,\ \operatorname{LLINK}[7]&=1, & \operatorname{RLINK}[7]&=5,\ \operatorname{LLINK}[5]&=7, & \operatorname{RLINK}[5]&=8,\ \operatorname{LLINK}[8]&=5, & \operatorname{RLINK}[8]&=2,\ \operatorname{LLINK}[2]&=8, & \operatorname{RLINK}[2]&=6,\ \operatorname{LLINK}[6]&=2, & \operatorname{RLINK}[6]&=4. \end{aligned} $$
Reindexed by node number,
$$ \boxed{ \begin{aligned} \operatorname{LLINK}[j] &= 3\ 8\ 4\ 6\ 7\ 2\ 1\ 5,\ \operatorname{RLINK}[j] &= 7\ 6\ 1\ 3\ 8\ 4\ 5\ 2, \end{aligned} } $$
and the root node is
$$ \boxed{4}. $$