TAOCP 2.3 Exercise 13
The path from node $X$ to the root consists of all nodes that are ancestors of $X$, including $X$ itself and the root.
Exercise 13. [**] [10] Suppose that node X is numbered $a_1.a_2.\cdots.a_k$ in the Dewey decimal system; what are the Dewey numbers of the nodes in the path from X to the root (see exercise 3)?
Verified: no
Solve time: 32s
The path from node $X$ to the root consists of all nodes that are ancestors of $X$, including $X$ itself and the root. If $X$ has Dewey number $a_1.a_2.\cdots.a_k$, then its parent has number $a_1.a_2.\cdots.a_{k-1}$, the grandparent has number $a_1.a_2.\cdots.a_{k-2}$, and so on, until the root, which has number $a_1$. Therefore, the sequence of Dewey numbers along the path from $X$ to the root is
$a_1.a_2.\cdots.a_k, \quad a_1.a_2.\cdots.a_{k-1}, \quad \ldots, \quad a_1.a_2, \quad a_1.$
Each step consists of removing the last component of the current Dewey number. There are exactly $k$ such steps, corresponding to the $k-1$ ancestors of $X$ plus $X$ itself. This completes the description. ∎