TAOCP 2.3.2 Exercise 1

Let $B$ be a binary tree.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.2: Binary Tree Representation of Trees

Exercise 1. [20] The text gives a formal definition of B(F), the binary tree corresponding to a forest F. Give a formal definition that reverses the process; in other words, define F(B), the forest corresponding to a binary tree B.

Verified: no
Solve time: 39s

Solution

Let $B$ be a binary tree. We define the corresponding forest $F(B)$ recursively so that it reverses the definition of $B(F)$.

a) If $B$ is empty, then

$$ F(B)=(). $$

That is, $F(B)$ is the empty forest.

b) If $B$ is nonempty and has root $R$, left subtree $L$, and right subtree $M$, first form the forests

$$ F(L)=(T_{11},T_{12},\ldots,T_{1m}), $$

and

$$ F(M)=(T_2,T_3,\ldots,T_n). $$

Define a tree $T_1$ whose root is $R$ and whose subtrees are precisely

$$ T_{11},T_{12},\ldots,T_{1m}. $$

Then define

$$ F(B)=(T_1,T_2,\ldots,T_n). $$

This construction is the exact inverse of the definition of $B(F)$ given in the text. Indeed, if

$$ F=(T_1,T_2,\ldots,T_n), $$

then by definition the root of $B(F)$ is $\operatorname{root}(T_1)$, its left subtree is the binary tree corresponding to the forest of subtrees of $T_1$, and its right subtree is the binary tree corresponding to $(T_2,\ldots,T_n)$. Applying the recursive definition above reconstructs $T_1$ from the left subtree and reconstructs $(T_2,\ldots,T_n)$ from the right subtree, yielding the original forest $F$.

Conversely, starting with a binary tree $B$, the construction of $F(B)$ produces a first tree whose root is the root of $B$ and whose subtrees come from the left subtree of $B$; the remaining trees of the forest come from the right subtree of $B$. Applying the definition of $B(F)$ then restores the original root, left subtree, and right subtree, hence reproduces $B$.

Therefore $F(B)$ is uniquely determined by the recursive rules above and is the inverse of the natural correspondence.

$$ \boxed{ \begin{aligned} F(\emptyset)&=(),\[2mm] F(B)&=(T_1,T_2,\ldots,T_n), \end{aligned} } $$

where $T_1$ has root equal to the root of $B$, its subtrees are the trees of $F(\text{left subtree of }B)$, and $(T_2,\ldots,T_n)=F(\text{right subtree of }B)$.

This completes the proof.

∎