TAOCP 2.3.2 Exercise 9

Let $F$ be a forest containing $t$ trees.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.3.2: Binary Tree Representation of Trees

Exercise 9. [M21] Show that the total number of nonterminal nodes in a forest has a simple relation to the total number of right links equal to Λ in the corresponding unthreaded binary tree.

Verified: yes
Solve time: 2m27s

Solution

Let $F$ be a forest containing $t$ trees. Under the natural correspondence between forests and binary trees, each node of $F$ becomes a node of the corresponding unthreaded binary tree $B(F)$.

Recall the correspondence:

  • The left link of a node in $B(F)$ points to its leftmost child in $F$.
  • The right link of a node in $B(F)$ points to its next sibling in $F$.

We shall count the right links of $B(F)$.

Let a node $v$ of $F$ have $k$ children.

  • If $k=0$, $v$ is terminal and contributes no right links.
  • If $k>0$, $v$ is nonterminal. Its children form an ordered list

$$ c_1,c_2,\ldots,c_k. $$

In $B(F)$, the sibling chain

$$ c_1 \to c_2 \to \cdots \to c_k $$

is represented by right links. Hence these children contribute exactly

$$ k-1 $$

right links.

Therefore the total number of right links in $B(F)$ is obtained by summing $k-1$ over all nonterminal nodes.

Let the nonterminal nodes be $v_1,\ldots,v_m$, and let $k_i$ be the number of children of $v_i$. Then

$$ R=\sum_{i=1}^{m}(k_i-1) =\left(\sum_{i=1}^{m}k_i\right)-m, $$

where $R$ denotes the total number of right links.

Now $\sum k_i$ is the total number of parent-child edges in the forest. If the forest contains $N$ nodes and $t$ trees, the number of edges is

$$ N-t, $$

since each tree with $n_j$ nodes has $n_j-1$ edges, and

$$ \sum_j (n_j-1)=N-t. $$

Hence

$$ R=(N-t)-m. $$

Let $L$ be the number of terminal nodes. Since $N=m+L$,

$$ R=(m+L-t)-m=L-t. $$

Thus

$$ \boxed{R=L-t.} $$

Equivalently,

$$ \boxed{L=R+t.} $$

Using $N=m+L$, we may also write

$$ m=N-t-R. $$

Therefore the simple relation is that the number of right links in the unthreaded binary tree equals the number of terminal nodes of the forest minus the number of trees in the forest:

$$ \boxed{\text{right links}=\text{terminal nodes}-\text{trees}.} $$

Since $m=N-L$, this also determines the number of nonterminal nodes.

$\square$