= Solution
A <trie> node needs a terminal flag as well as its children: a stored word can also be the prefix of a longer stored word.
``
TYPE Trie = POINTER TO Node;
Node = RECORD
terminal: BOOLEAN;
child: ARRAY 26 OF Trie
END;
``
Index zero denotes `a`, index 25 denotes `z`; <null pointers> denote absent branches. The <set> represented by a nonnull node consists of the empty <string> if `terminal` is true, together with every child's words prefixed by that child's letter. \b[Represent the empty <set> by `NIL`.] The singleton containing the empty <string> instead has a terminal root and no children.
\b[The declarations alone do not force a unique representation.] A nonterminal leaf, or a whole branch without terminal descendants, contributes no word. To obtain uniqueness up to pointer addresses, impose a <representation invariant>: the structure is a finite <rooted tree>, and each allocated node lies on a path to a terminal node. Then precisely the prefixes of stored words exist, all flags are determined, and the empty <set> has only the `NIL` representation. The insertion procedures below preserve this invariant when starting with such a <trie>.
Back to article page
