TAOCP 2.3.4.2 Exercise 10
Let $R$ be the original root, and let V_j,V_{a_1},V_{a_2},\ldots,V_{a_t},R be the unique oriented path from $V_j$ to $R$.
Section 2.3.4.2: Oriented Trees
Exercise 10. [**] $$22$$ An oriented tree with vertices $V_1,\ldots,V_n$ can be represented inside a computer by using a table $P[1],\ldots,P[n]$ as follows: If $V_j$ is the root, $P[j]=0$; otherwise $P[j]=k$, if the arc $e[V_j]$ goes from $V_j$ to $V_k$. (Thus $P[1],\ldots,P[n]$ is the same as the "parent" table used in Algorithm 2.3.3E.)
The text shows how a free tree can be converted into an oriented tree by choosing any desired vertex to be the root. Consequently, it is possible to start with an oriented tree that has root $R$, then to convert this into a free tree by neglecting the orientation of the arcs, and finally to assign new orientations, obtaining an oriented tree with any specified vertex as the root. Design an algorithm that performs this transformation: Starting with a table $P[1],\ldots,P[n]$, representing an oriented tree, and given an integer $j$, $1\le j\le n$, design the algorithm to transform the $P$ table so that it represents the same free tree but with $V_j$ as the root.
Verified: yes
Solve time: 1m06s
Let $R$ be the original root, and let
$$ V_j,V_{a_1},V_{a_2},\ldots,V_{a_t},R $$
be the unique oriented path from $V_j$ to $R$. In the table representation,
$$ P[j]=a_1,\quad P[a_1]=a_2,\quad \ldots,\quad P[a_t]=R,\quad P[R]=0. $$
To make $V_j$ the new root, reverse the parent links on this path and leave all other entries unchanged:
$$ P[R]\leftarrow a_t, $$
$$ P[a_t]\leftarrow a_{t-1}, $$
$$ \cdots $$
$$ P[a_1]\leftarrow j, $$
$$ P[j]\leftarrow 0. $$
These assignments reverse every arc on the path from $V_j$ to $R$ and affect no other arc. The underlying free tree is therefore unchanged. Every vertex not on the path retains its parent. Every vertex on the path, except $V_j$, receives as parent its former child on the path. Hence all arcs are oriented toward $V_j$, and $V_j$ is the unique vertex whose parent entry is $0$. The resulting table represents the same free tree with root $V_j$.
If the path from $V_j$ to $R$ contains $t+1$ arcs, the transformation requires exactly $t+2$ replacements, namely the assignments to $P[R]$, $P[a_t],\ldots,P[a_1]$, and $P[j]$. Since each of these entries changes value, no algorithm can perform the transformation with fewer replacements. Thus the above method is optimal. ∎