A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Storing Words

Now, the point of our trie is to store words. Let’s see how the following trie stores the words, “ace,” “bad,” and “cat” as shown in the diagram.

This trie stores the three words by turning each character of each word into its own trie node. If you start with the root node and follow its "a" key, for example, it points to a child node containing a key of "c". The "c" key, in turn, points to a node that contains a key of "e". When we string these three characters together, we get the word "ace".

With this pattern, you can see how the trie also stores the words "bad" and "cat".

You’ll note that the final characters in these words actually ...