TAOCP 2.3.2 Exercise 5

Let the roots of the trees of the forest $F$ be regarded as siblings arranged from left to right.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.2: Binary Tree Representation of Trees

Exercise 5. [23] Another correspondence between forests and binary trees could be defined by letting RLINK(P) point to the rightmost child of NODE(P), and LLINK(P) to the nearest sibling on the left. Let F be a forest that corresponds in this way to a binary tree B. What order, on the nodes of B, corresponds to (a) preorder (b) postorder on F?

Verified: yes
Solve time: 4m11s

Let the roots of the trees of the forest $F$ be regarded as siblings arranged from left to right. Under the modified correspondence,

$$ RLINK(P)=\text{rightmost child of }P, \qquad LLINK(P)=\text{nearest sibling on the left}. $$

Thus, if a node $R$ has children

$$ C_1,C_2,\ldots,C_m $$

from left to right in the forest, then in the binary tree $B$

$$ R.RLINK=C_m,\qquad C_m.LLINK=C_{m-1},\qquad \dots,\qquad C_2.LLINK=C_1. $$

Hence the chain

$$ C_m \xrightarrow{LLINK} C_{m-1} \xrightarrow{LLINK}\cdots \xrightarrow{LLINK} C_1 $$

encodes the children of $R$.

The question is not asking for an ordinary binary-tree traversal. We must determine the order of the nodes of $B$ that reproduces preorder and postorder of the forest.

(a) Preorder

Let $P(F)$ denote the preorder sequence of the forest $F$.

Suppose $R$ is a root whose children are $C_1,\ldots,C_m$. Then

$$ P(R)=R,;P(C_1),;P(C_2),\ldots,P(C_m). $$

In the binary tree, the node corresponding to $C_m$ has left child $C_{m-1}$, whose left child is $C_{m-2}$, and so on.

Define recursively an order $\Pi$ on the nodes of $B$ by

$$ \Pi(X)= \begin{cases} \varnothing, & X=\Lambda,\[2mm] X,;\Pi(LLINK(X)),;\Pi(RLINK(X)), & X\neq\Lambda . \end{cases} $$

That is:

  1. visit the node;
  2. traverse the $LLINK$-subtree;
  3. traverse the $RLINK$-subtree.

Let us verify this on the children of $R$.

Starting at $C_m$,

$$ \Pi(C_m) = \Pi(C_1),\Pi(C_2),\ldots,\Pi(C_m), $$

because the recursive traversal of the $LLINK$-chain reaches $C_1$ first and then unwinds back through $C_2,\ldots,C_m$. For example, when $m=2$,

$$ \Pi(C_2)=C_2,\Pi(C_1), $$

and after expanding recursively each subtree one obtains

$$ P(C_1),P(C_2), $$

not the reversed order.

Consequently,

$$ \Pi(R) = R,;P(C_1),P(C_2),\ldots,P(C_m), $$

which is exactly the forest preorder.

Therefore preorder on $F$ corresponds to the binary-tree order

$$ \boxed{\text{node},;LLINK\text{-subtree},;RLINK\text{-subtree}.} $$

(b) Postorder

Let $Q(F)$ denote the postorder sequence of the forest.

For a root $R$ with children $C_1,\ldots,C_m$,

$$ Q(R) = Q(C_1),Q(C_2),\ldots,Q(C_m),R. $$

Define recursively an order $\Omega$ on $B$ by

$$ \Omega(X)= \begin{cases} \varnothing, & X=\Lambda,\[2mm] \Omega(LLINK(X)),;\Omega(RLINK(X)),;X, & X\neq\Lambda . \end{cases} $$

That is:

  1. traverse the $LLINK$-subtree;
  2. traverse the $RLINK$-subtree;
  3. visit the node.

Applying this to the chain

$$ C_m \to C_{m-1}\to\cdots\to C_1, $$

the recursive descent along $LLINK$ reaches $C_1$ first and yields

$$ Q(C_1),Q(C_2),\ldots,Q(C_m). $$

After all children have been processed, $R$ is visited. Hence

$$ \Omega(R) = Q(C_1),Q(C_2),\ldots,Q(C_m),R, $$

which is exactly the forest postorder.

Therefore postorder on $F$ corresponds to the binary-tree order

$$ \boxed{LLINK\text{-subtree},;RLINK\text{-subtree},;\text{node}.} $$

Answer

If $B$ is the binary tree obtained from $F$ by

$$ RLINK=\text{rightmost child},\qquad LLINK=\text{nearest left sibling}, $$

then:

$$ \boxed{\text{Preorder on }F ;\longleftrightarrow; (\text{node},,LLINK,,RLINK)} $$

and

$$ \boxed{\text{Postorder on }F ;\longleftrightarrow; (LLINK,,RLINK,,\text{node})}. $$

These are the analogues of preorder and postorder for the modified forest-to-binary-tree correspondence. ∎