A tree shaped like a prefix

A search box should suggest completions as you type. A hash set of words answers "is this a word" instantly and cannot answer "which words start with these three letters" without checking all of them.

A trie stores the shared prefixes once, so that question becomes a walk.

The structure

Each edge is a character and each path from the root spells a prefix.

        root
       /    \
      c      d
      |      |
      a      o
     / \     |
    r   t    g*
    |   |
    d*  *

A marker says a node ends a real word, which is how "cat" and "cart" coexist without "car" being a word unless it is.

class Trie:
    def __init__(self):
        self.children = {}
        self.is_word = False

    def insert(self, word):
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
        node.is_word = True

    def starts_with(self, prefix):
        node = self
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node        # everything below is a completion

The costs

The third row is the reason to use one. The hash set has to examine every word it holds.

Note the lookup does not depend on how many words are stored, only on the length of this one. A trie with ten million words finds a five letter word in five steps.

What it costs in memory

A node per character per distinct prefix, each with a map of children. That is substantially more memory than a plain list of strings, and it is the reason tries are not the default.

Two fixes exist. A compressed trie merges chains of single child nodes into one edge holding several characters. A DAWG also merges identical suffixes, which shrinks a dictionary dramatically at the cost of no longer being able to store a value per word.

Where they are actually used

Autocomplete and spell checking. IP routing tables, where the question is longest matching prefix and that is exactly a trie walk. Word games. And T9 predictive text, which is where most people first met one without knowing.