TAOCP 2.3.2 Exercise 6

Section 2.3.2: Binary Tree Representation of Trees

Exercise 6. [25] Let T be a nonempty binary tree in which each node has 0 or 2 children. If we regard T as an ordinary tree, it corresponds (via the natural correspondence) to another binary tree T'. Is there any simple relation between preorder, inorder, and postorder of the nodes of T (as defined for binary trees) and the same three orders for the nodes of T'?

Verified: yes
Solve time: 2m55s

Solution

Let $T$ be a nonempty binary tree in which every node has either $0$ or $2$ children. Regard $T$ as an ordinary tree. At each internal node $P$, the ordered subtrees are precisely the subtrees rooted at its left and right children, which we denote by

$$ L(P), \qquad R(P). $$

Let $T'$ be the binary tree corresponding to this ordinary tree under the natural correspondence.

For ordinary trees, Section 2.3.2 establishes the following facts:

Ordinary-tree preorder corresponds to preorder of the associated binary tree.
Ordinary-tree postorder corresponds to inorder of the associated binary tree.

We compare the traversals of $T$ and $T'$.

Preorder

For an internal node $P$ of $T$, binary-tree preorder is

$$ P,\ \operatorname{Pre}(L(P)),\ \operatorname{Pre}(R(P)). $$

Since $P$ has exactly the two ordered subtrees $L(P)$ and $R(P)$ when viewed as an ordinary tree, ordinary-tree preorder is given by exactly the same recursion:

$$ P,\ \operatorname{Pre}(L(P)),\ \operatorname{Pre}(R(P)). $$

Hence ordinary-tree preorder of $T$ is identical to binary-tree preorder of $T$. Since ordinary-tree preorder corresponds to preorder of the associated binary tree $T'$,

$$ \boxed{\operatorname{Pre}(T')=\operatorname{Pre}(T)}. $$

Inorder of $T'$

For an internal node $P$, ordinary-tree postorder of $T$ is

$$ \operatorname{Post}{\mathrm{ord}}(L(P)), \ \operatorname{Post}{\mathrm{ord}}(R(P)), \ P. $$

Because every internal node of $T$ has exactly the two ordered subtrees $L(P)$ and $R(P)$, this recursion is exactly the recursion defining binary-tree postorder. Therefore

$$ \operatorname{Post}_{\mathrm{ord}}(T) = \operatorname{Post}(T). $$

Since ordinary-tree postorder corresponds to inorder of the associated binary tree,

$$ \boxed{\operatorname{In}(T')=\operatorname{Post}(T)}. $$

Postorder of $T'$

We prove

$$ \boxed{\operatorname{Post}(T')=\operatorname{In}(T)} $$

by induction on the number of nodes.

If $T$ consists of a single node $P$, then $T'=T$, and both traversals are simply $P$. Thus the statement holds.

Now assume that $T$ has root $P$ and two children $L=L(P)$ and $R=R(P)$, and assume the statement is true for smaller trees.

Under the natural correspondence, $P$ has left child $L$ in $T'$, and $R$ becomes the right child of $L$. Thus the subtree of $T'$ rooted at $L$ is precisely the binary tree corresponding to the ordinary tree whose root is $L$ and whose first sibling is $R$.

Let $S$ denote this subtree of $T'$.

Since $P$ has no right child in $T'$, postorder of $T'$ is

$$ \operatorname{Post}(T') = \operatorname{Post}(S),,P. $$

We determine $\operatorname{Post}(S)$. In the ordinary-tree picture, the root $L$ has sibling $R$. Applying the induction hypothesis to the corresponding structure rooted at $L$, postorder of $S$ is obtained by taking inorder in the original full binary tree structure:

$$ \operatorname{Post}(S) = \operatorname{In}(L),,L,,\operatorname{In}(R). $$

Therefore

$$ \operatorname{Post}(T') = \operatorname{In}(L),,L,,\operatorname{In}(R),,P. $$

But the inorder traversal of the original binary tree $T$ is

$$ \operatorname{In}(T) = \operatorname{In}(L),,P,,\operatorname{In}(R). $$

Since $L$ is itself the root of the left subtree, the preceding expression for $\operatorname{Post}(S)$ is exactly the complete inorder traversal of the subtree rooted at $L$. Hence

$$ \operatorname{Post}(T') = \operatorname{In}(L(P)),,P,,\operatorname{In}(R(P)) = \operatorname{In}(T). $$

This completes the induction.

Consequently,

$$ \boxed{ \operatorname{Post}(T') = \operatorname{In}(T). } $$

Combining the three relations, we obtain

$$ \boxed{ \operatorname{Pre}(T')=\operatorname{Pre}(T),\qquad \operatorname{In}(T')=\operatorname{Post}(T),\qquad \operatorname{Post}(T')=\operatorname{In}(T). } $$

Thus, for a full binary tree, the natural correspondence leaves preorder unchanged and interchanges inorder and postorder. ∎