TAOCP 2.3 Exercise 3
We proceed by induction on the number of nodes in the tree.
Exercise 3. [**] [M20] Prove rigorously from the definitions that for every node X in a tree there is a unique path up to the root, namely a unique sequence of $k \ge 1$ nodes X_1, X_2, ..., X_k such that X_1 is the root of the tree, X_k = X, and X_j is the parent of X_{j+1} for $1 \le j < k$. (This proof will be typical of the proofs of nearly all the elementary facts about tree structures.) Hint: Use induction on the number of nodes in the tree.
Verified: no
Solve time: 29s
We proceed by induction on the number of nodes in the tree.
If the tree has one node, that node is the root. For the unique node $X$, the required sequence is simply $X_1=X$, with $k=1$. This sequence is unique.
Assume the theorem holds for all trees having fewer than $n$ nodes, where $n>1$, and let $T$ be a tree with $n$ nodes. Let $R$ be the root of $T$, and let $X$ be any node of $T$.
If $X=R$, the unique path is again the one-term sequence $X_1=R$.
If $X\ne R$, then by the definition of a tree, $X$ has a unique parent $P$. Remove the root $R$ and all branches incident with it. The remaining graph decomposes into disjoint trees, one for each child of $R$. Since $X\ne R$, the node $X$ lies in exactly one of these smaller trees, and this tree contains fewer than $n$ nodes. By the induction hypothesis, within that smaller tree there is a unique sequence
$$ X_1,X_2,\ldots,X_k $$
such that $X_1$ is the root of the smaller tree, $X_k=X$, and $X_j$ is the parent of $X_{j+1}$ for $1\le j<k$. The root of this smaller tree is a child of $R$, hence its parent in $T$ is $R$. Therefore
$$ R,X_1,X_2,\ldots,X_k $$
is a path from the root of $T$ to $X$.
Uniqueness remains to be proved. Suppose
$$ R,Y_2,\ldots,Y_m=X $$
is another path from the root to $X$. Since $X\ne R$, the second node $Y_2$ must be a child of $R$, and all subsequent nodes must lie in the same smaller tree rooted at $Y_2$. Since $X$ belongs to exactly one such smaller tree, necessarily $Y_2=X_1$. By the induction hypothesis, the remainder of the path inside that smaller tree is unique; hence
$$ Y_2,\ldots,Y_m=X_1,\ldots,X_k. $$
Therefore the entire path is unique.
This completes the proof.
∎