TAOCP 7.2.1.6 Exercise 113
Let $F$ be a forest with $n$ nodes and let $F^E$ be its extended forest, formed by adjoining a new root node $\rho$ whose children are the roots of the trees of $F$ in their left-to-right order, as in...
Section 7.2.1.6: Generating All Trees
Exercise 113. ▶ [20] How do prepostorder and postpreorder of a forest $F$ relate to prepostorder and postpreorder of the extended forest $F^E$? (See exercise 13.)
Verified: no
Solve time: 3m39s
Solution
Let $F$ be a forest with $n$ nodes and let $F^E$ be its extended forest, formed by adjoining a new root node $\rho$ whose children are the roots of the trees of $F$ in their left-to-right order, as in Section 7.2.1.6.
Let $\operatorname{pre}(x)$ and $\operatorname{post}(x)$ denote preorder and postorder numbers in a forest. In $F^E$, the new root $\rho$ is the first node in preorder and the last node in postorder. Every other node keeps the same relative position inside its original tree; only the global indexing shifts.
Let $V(F)={1,\ldots,n}$ and $V(F^E)={\rho}\cup V(F)$.
In $F^E$, preorder traversal visits $\rho$ first, then traverses each tree of $F$ in preorder. Hence the preorder sequence of $F^E$ is
$$ \rho,; v_1,; v_2,; \ldots,; v_n, $$
where $v_1,\ldots,v_n$ is the preorder sequence of $F$.
Postorder traversal of $F^E$ visits all nodes of $F$ first, and visits $\rho$ last. Hence the postorder sequence of $F^E$ is
$$ v_1,; v_2,; \ldots,; v_n,; \rho, $$
where $v_1,\ldots,v_n$ is the postorder sequence of $F$.
Now define the prepostorder sequence of a forest as the list of nodes ordered by increasing preorder number, and similarly the postpreorder sequence as the list ordered by increasing postorder number.
For $F^E$, preorder numbers satisfy
$$ \operatorname{pre}{F^E}(\rho)=1,\qquad \operatorname{pre}{F^E}(v)=\operatorname{pre}_{F}(v)+1 \quad (v\in V(F)). $$
Thus the prepostorder of $F^E$ begins with $\rho$, followed by the nodes of $F$ in exactly the same relative order as in the prepostorder of $F$, with all nodes shifted by one position in their preorder labels.
Similarly, postorder numbers satisfy
$$ \operatorname{post}{F^E}(v)=\operatorname{post}{F}(v),\qquad \operatorname{post}_{F^E}(\rho)=n+1, $$
so the postpreorder of $F^E$ coincides with that of $F$ followed by $\rho$ at the end.
Therefore the relationships are:
The prepostorder of $F^E$ is obtained from the prepostorder of $F$ by inserting the new root $\rho$ as the first element and increasing all preorder indices of nodes of $F$ by $1$.
The postpreorder of $F^E$ is obtained from the postpreorder of $F$ by appending the new root $\rho$ as the last element, with all postorder indices of nodes of $F$ unchanged.
This completes the proof. ∎