TAOCP 2.3 Exercise 15
A natural notation for nodes of a binary tree extends the Dewey decimal system by encoding each branching choice as a binary digit.
Exercise 15. ▶ [**] [20] Invent a notation for the nodes of binary trees, analogous to the Dewey decimal notation for nodes of trees.
Verified: yes
Solve time: 36s
A natural notation for nodes of a binary tree extends the Dewey decimal system by encoding each branching choice as a binary digit. Let the root be numbered $1$. For any node numbered $\alpha$, its left child is numbered $\alpha.0$ and its right child is numbered $\alpha.1$. More generally, any node is identified by a finite sequence of digits $0$ and $1$ appended to $1$, where each digit indicates the path taken from the root: $0$ for left, $1$ for right. This numbering uniquely identifies each node and preserves the hierarchical structure of the tree, since the prefix of a node number corresponds to its ancestors, analogous to the Dewey decimal notation.
The proposed notation satisfies a simple recursive condition analogous to Exercise 2.3.14: if $\alpha.b$ is in the set of node numbers, then $\alpha$ is also in the set. Conversely, each sequence of $0$’s and $1$ appended to the root corresponds to a distinct node in the binary tree. This construction allows immediate determination of the parent of any node (by removing the last digit) and its children (by appending $0$ or $1$), providing a complete and unambiguous labeling system for binary trees. ∎