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

Trie Search

The most classic trie operation is search, namely, determining whether a string is found in the trie. There are two flavors of search: we can search to see whether the string is a complete word, or we can search to see whether the string is at least a word prefix (that is, the beginning of a word). These two versions are similar, but we’ll implement the latter one, where our search will look for prefixes. This search will end up finding complete words as well, since a complete word is at least as good as a prefix.

The algorithm for prefix search performs the following steps (they’ll become clearer when we walk though an example that follows):

1. We establish a variable called currentNode. At the beginning of our algorithm, this points ...