TAOCP 2.3.3 Exercise 19

We are asked to reason about **descendant number sequences** in preorder.

taocpmathematicsalgorithmsvolume-1math-hard

Section 2.3.3: Other Representations of Trees

Exercise 19. [M27] Instead of using SCOPE links in (5), we could simply list the number of descendants of each node, in preorder:

$$ \begin{array}{c|cccccccccc} \text{DESC} & 3 & 0 & 1 & 0 & 5 & 1 & 0 & 1 & 0 & 0\ \text{INFO} & A & B & C & K & D & E & H & F & J & G \end{array} $$

Let d_1 d_2 ... d_n be the sequence of descendant numbers of a forest, obtained in this way.

a) Show that k + d_k <= n for 1 <= k <= n, and that k <= j <= k + d_k implies j + d_j <= k + d_k.

b) Conversely, prove that if d_1 d_2 ... d_n is a sequence of nonnegative integers satisfying the conditions of (a), it is the sequence of descendant numbers of a forest.

c) Suppose d_1 d_2 ... d_n and d'_1 d'_2 ... d'_n are the descendant number sequences for two forests. Prove that there is a third forest whose descendant numbers are

$$ \min(d_1,d'_1)\ \min(d_2,d'_2)\ \cdots\ \min(d_n,d'_n). $$

Verified: yes
Solve time: 2m24s

Solution

We are asked to reason about descendant number sequences in preorder. Let the preorder of a forest with $n$ nodes be numbered $1,2,\dots,n$, and let $d_1,d_2,\dots,d_n$ be the number of descendants of each node, including the node itself. Let $\text{INFO}[j]$ denote the label of node $j$.

Part (a)

Claim. For all $1 \le k \le n$,

  1. $k + d_k - 1 \le n$, and
  2. if $k \le j \le k + d_k - 1$, then $j + d_j - 1 \le k + d_k - 1$.

Proof.

  1. Consider node $k$ in preorder. Its subtree consists of itself and all its descendants in preorder. The last node of this subtree occurs at position $k + d_k - 1$. Since there are only $n$ nodes, we must have

$$ k + d_k - 1 \le n. $$

  1. Let $j$ be any node in the subtree of $k$ in preorder, so $k \le j \le k + d_k - 1$. The subtree of $j$ is entirely contained within the subtree of $k$. Therefore, the last node of $j$'s subtree in preorder is at position $j + d_j - 1$, and it cannot extend beyond the last node of $k$'s subtree. Hence

$$ j + d_j - 1 \le k + d_k - 1. $$

This proves the inequalities.

Part (b)

Claim. Conversely, if a sequence of nonnegative integers $d_1,\dots,d_n$ satisfies the inequalities in part (a), then there exists a forest whose preorder descendant numbers are exactly $d_1,\dots,d_n$.

Proof.

We construct the forest recursively:

  1. If $n=0$, the empty sequence corresponds to the empty forest.
  2. Otherwise, let the first node be the root of a tree. Its subtree has $d_1$ nodes: node 1 itself plus $d_1 - 1$ descendants.
  3. Let $S$ denote the nodes $2,3,\dots,d_1$. Consider the sequence $d_2,\dots,d_{d_1}$ restricted to these nodes. By the inequality in part (a), for each $j$ in $2,\dots,d_1$,

$$ j + d_j - 1 \le 1 + d_1 - 1 = d_1, $$

so all descendants of these nodes lie within the first $d_1$ nodes. By induction on the length of the sequence, we can construct a subtree rooted at node 1 whose preorder descendant numbers are $d_1,\dots,d_{d_1}$.

  1. The remaining sequence $d_{d_1+1},\dots,d_n$ satisfies the same inequalities by shifting indices. By induction, we can construct a forest on these remaining nodes.

Concatenating the root tree with the remaining forest produces a forest whose preorder descendant numbers are exactly $d_1,\dots,d_n$.

Part (c)

Claim. Let $d_1,\dots,d_n$ and $d'_1,\dots,d'_n$ be two valid preorder descendant sequences. Define

$$ \delta_j = \min(d_j,d'_j), \quad 1 \le j \le n. $$

Then $\delta_1,\dots,\delta_n$ is also a valid preorder descendant sequence.

Proof.

We must verify that $\delta_1,\dots,\delta_n$ satisfies the inequalities of part (a):

  1. Since $d_j$ and $d'_j$ satisfy part (a),

$$ j + d_j - 1 \le n, \quad j + d'_j - 1 \le n \implies j + \delta_j - 1 \le n. $$

  1. If $k \le j \le k + \delta_k - 1$, then $j \le k + d_k - 1$ and $j \le k + d'_k - 1$. Therefore,

$$ j + d_j - 1 \le k + d_k - 1, \quad j + d'_j - 1 \le k + d'_k - 1. $$

Hence

$$ j + \delta_j - 1 = j + \min(d_j,d'_j) - 1 \le \min(k + d_k - 1, k + d'_k - 1) = k + \delta_k - 1. $$

Thus the sequence $\delta_1,\dots,\delta_n$ satisfies the inequalities in part (a). By part (b), it corresponds to a valid forest.

Example

For the sequence given in the exercise:

$$ \text{DESC} = 3,0,1,0,5,1,0,1,0,0 $$

Check part (a):

  • Node 1: $1+3-1=3 \le 10$
  • Node 2: $2+0-1=1 \le 3$ (node 2 is within subtree of node 1)
  • Node 3: $3+1-1=3 \le 3$ (node 3 is within subtree of node 1)

and so on. All inequalities hold.

If we take another valid sequence $d'_j$ of the same length, the componentwise minimum produces another valid sequence, as argued in part (c).

∎