TAOCP 6.3 Exercise 1
In a tree, leaves are nodes with no descendants.
Section 6.3: Digital Searching
Exercise 1. [00] [00] Ifa tree has leaves, what does a trie have?
Verified: no
Solve time: 4m
In a tree, leaves are nodes with no descendants.
In a trie, the analogue is not structural absence of children but the presence of a terminal designation: nodes that correspond to complete keys (words) are marked as terminal nodes, whether or not they have outgoing links. Thus the role of leaves is replaced by the set of terminal nodes representing stored keys. ∎