Chapter 17
It Doesn’t Hurt to Trie

Did you ever wonder how your smartphone’s autocomplete feature works? Autocomplete is the feature you see when you start typing “catn” and your phone suggests that the word you’re about to type is either “catnip” or “catnap”. (Yes, I text my friends about catnip all the time.)

For this to work, your phone has access to an entire dictionary of words. But what data structure are these words stored in?

Let’s imagine, for a moment, that all the words in the English language are stored within an array. If the array were unsorted, we’d have to search every word in the dictionary to find all words that start with “catn”. This is O(N), and a very slow operation considering that N is a pretty large number in this case, as it’s the number of all the words in the dictionary.

A hash table wouldn’t help us either, as it hashes the entire word to determine where in memory the value should be stored. As the hash table wouldn’t have a “catn” key, we’d have no easy way to locate “catnip” or “catnap” within the hash table.

Things improve greatly if we store the words inside an ordered array. If the array contained all the words in alphabetical order, we could use binary search to find a word beginning with “catn” in O(log N) time. And while O(log N) isn’t bad, we can do even better. In fact, if we use a special tree-based data structure, we can approach O(1) speeds in finding our desired words.

The examples in this chapter show how tries can be used for applications dealing with text, as tries allow for important features such as autocomplete and autocorrect. However, tries have other uses as well, including applications involving IP addresses or phone numbers.