TAOCP 2.3 Exercise 14

Section 2.3: Trees

Exercise 14. [**] [M22] Let S be any nonempty set of elements having the form "1.a_1...a_k", where $k \ge 0$ and $a_1, \ldots, a_k$ are positive integers. Show that S specifies a tree when it is finite and satisfies the following condition: "If $\alpha.m$ is in the set, then so is $\alpha.(m - 1)$ if $m > 1$, or $\alpha$ if $m = 1$." (This condition is clearly satisfied in the Dewey decimal notation for a tree; therefore it is another way to characterize tree structure.)

Verified: no
Solve time: 45s

Let the elements of $S$ be regarded as nodes, and define the parent of a node $\alpha.m$ to be $\alpha$ when $m=1$, and define the nodes $\alpha.1,\alpha.2,\ldots$ to be the children of $\alpha$ whenever they belong to $S$.

Since $S$ is finite and nonempty, repeated application of the stated condition to any node eventually decreases the last component to $1$ and then removes it. Therefore every node has a finite chain of ancestors terminating at $1$, and $1\in S$. The condition also implies that if $\alpha.m\in S$, then $\alpha.j\in S$ for every $1\le j<m$; hence the children of any node $\alpha$ are precisely $\alpha.1,\alpha.2,\ldots,\alpha.r$ for some $r\ge0$. Each node other than $1$ has exactly one parent, namely the unique string obtained by either replacing the final component $m>1$ by $m-1$ repeatedly until $1$ is reached and then deleting that final $1$, or, equivalently, by the inverse of the construction above. Thus every node except $1$ has a unique immediate predecessor, while $1$ has none.

Consequently there is a unique path from every node to the root $1$, and no cycle can occur since each step toward the root shortens the Dewey notation after finitely many applications. Hence the graph determined by these parent-child relations is connected and acyclic. Therefore $S$ specifies a tree. This completes the proof.

∎