A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

Chapter 17It 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, ...