Tries and prefix trees

What this chapter covers

Every tree so far has been keyed by whole values — a node holds a number, and you compare against it. A trie throws that out and keys by the characters of strings instead: each edge is a single letter, each path from the root spells a prefix, and words that share a prefix share the same branch. That reorganization makes one operation almost free — "is there any word starting with these letters?" — answered by walking down the letters, independent of how many words are stored. It's the structure behind autocomplete, spell-checkers, and IP routing tables, and its cost is measured in the length of the key, not the size of the dictionary. This chapter builds it, watches words grow a shared tree, and shows it leaving a naive scan far behind.

A bit of history

The trie was invented at the turn of the 1960s, and even its name is a small puzzle. René de la Briandais described the structure in 1959, and Edward Fredkin named it in 1960, coining "trie" from the middle of "retrieval" — which is why the pedants pronounce it "tree" and everyone else says "try" to avoid the collision. Fredkin's insight was that for retrieving strings, you shouldn't compare whole keys at all; you should branch on one character at a time, so that common prefixes cost nothing extra. That idea turned out to be foundational for text processing: tries and their compressed variants underlie spell-checkers, autocomplete, the routing tables that forward every internet packet by longest-matching IP prefix, and the tokenizers inside search engines and compilers. Sixty years on, whenever software has to answer questions about the prefixes of a large set of strings, a trie is the classic answer.

The intuition

Imagine filing words not alphabetically in a list, but by walking a branching path: to store "card," you go down the c branch, then a, then r, then d, creating those steps if they don't exist. Now store "care" — the c-a-r path already exists, so you reuse it and only add the final e. The shared prefix "car" is stored exactly once, and the two words diverge only where they actually differ. Do this for a whole dictionary and you get a tree where every internal node is a shared prefix and every complete word is marked at the node where it ends.

That structure makes prefix questions trivial. To ask "does any word start with 'car'?" you just walk c-a-r and see if the path exists — you never look at a single stored word, and the cost is three steps whether the dictionary holds ten words or ten million. To autocomplete "car," you walk to that node and then collect every word-end in the subtree below it, visiting only the words that actually match. And searching for an exact word is the same walk, with one subtlety: reaching the end of the path isn't enough — the final node must be marked as a word, because "car" being stored gives you the path for "ca" too, even though "ca" may not be a word. The mark is what distinguishes a stored word from a mere prefix of one.

Complexity: how it scales

Insert, search, and starts_with are all $O(L)$ in the length of the key — you take one step per character. Autocomplete under a prefix is $O(L + m)$, where m is the total size of the matching words, because after the O(L) walk to the prefix node it visits exactly the matches and nothing else. None of these depend on N, the number of words, which is the headline. Space is the trie's soft spot: it stores one node per distinct prefix character, with a children map per node, so a trie can use more memory than a plain word list — though shared prefixes claw a lot of that back. The chart runs prefix queries against dictionaries of growing size:

The scan line climbs with the dictionary size — it re-reads every word on every query, O(N·L) — while the trie line stays comparatively flat, because each query only walks its own prefix. At 320000 words the trie answered 500 prefix queries about 8 times faster than the scan, and the gap widens with N, exactly as O(L) versus O(N·L) predicts.

What it's good at, what it isn't

The trie is the right structure when your questions are about prefixes of strings. Autocomplete, "all words starting with," spell-check suggestions, longest-prefix matching for IP routing, and dictionary lookups where you want to fail fast on impossible prefixes — all of these are what the trie makes cheap and a hash table can't do at all. It also keeps its keys in sorted order for free (a pre-order walk yields them alphabetically), and it can compress enormously when many keys share prefixes.

Where it's the wrong tool is plain membership. If all you ever ask is "is this exact word present?", a hash set answers in O(L) too — the length to hash the key — and uses far less memory than a trie's forest of nodes and child maps. Tries also struggle with large alphabets (a full Unicode child map per node is heavy) and with keys that share few prefixes, where the tree is nearly all branching and little sharing. The trie earns its memory only when prefixes are the question and sharing is real; otherwise a hash set is leaner.

The data, or the inputs

The face-off builds dictionaries of random words over a small alphabet (so prefixes are genuinely shared) and times prefix queries as the dictionary grows, to isolate the trie's independence from N. The animation inserts seven hand-picked words — cat, car, card, care, dog, do, dot — so you can watch the shared prefixes branch and the word-ends light up.

Build it, one function at a time

Insert walks the characters, creating nodes as needed, and marks the end:

def insert(self, word):
    """O(L) for a word of length L: walk down one character at a time, creating
    child nodes where the path doesn't exist yet. Words sharing a prefix reuse the
    same nodes — 'car' and 'card' share the first three."""
    node = self.root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    if not node.is_word:
        node.is_word = True
        self._n += 1

Search is the same walk, with the crucial check that the final node is marked a word:

def search(self, word):
    """O(L): follow the characters. The word is present only if the whole path
    exists AND its final node is marked a word-end — 'car' being stored doesn't
    mean 'ca' is a word, even though its path exists."""
    node = self._find(word)
    return node is not None and node.is_word

starts_with is the trie's superpower — just check that the prefix path exists:

def starts_with(self, prefix):
    """O(L): the trie's superpower. Is there ANY word with this prefix? Just check
    whether the path exists — you never look at the words themselves."""
    return self._find(prefix) is not None

def _find(self, s):
    node = self.root
    for ch in s:
        if ch not in node.children:
            return None
        node = node.children[ch]
    return node

And autocomplete walks to the prefix, then collects every word beneath it:

def words_with_prefix(self, prefix):
    """Autocomplete: walk to the prefix node, then collect every word-end below it.
    O(L + size of the subtree) — it visits only words that actually match, never the
    rest of the dictionary."""
    node = self._find(prefix)
    out = []
    if node is None:
        return out

    def dfs(n, suffix):
        if n.is_word:
            out.append(prefix + suffix)
        for ch, child in sorted(n.children.items()):
            dfs(child, suffix + ch)

    dfs(node, "")
    return out

Watch it work

Here's a trie built from seven words. The root (•) branches by first letter; green nodes mark where a complete word ends; orange highlights the path just inserted. Step through it and watch the sharing happen: "cat" lays down c-a-t, then "car" reuses c-a and only adds r, then "card" and "care" reuse c-a-r and branch at the last letter. On the other side, "do" is a word and a prefix of "dog" and "dot," so its node is both green (a word) and a branch point. The shared prefixes are stored exactly once — that sharing is the whole structure:

The complete code

Both versions in one place — flip between them. The from-scratch tab is the trie. The library tab is the naive alternative — scanning the word list for a prefix, plus a set for membership — because Python has no built-in trie (the third-party pygtrie fills that gap, and a trie is fundamentally just nested dictionaries).

"""The trie (prefix tree) — a tree keyed by the characters of strings rather than by
whole values. Each edge is one character, each root-to-node path spells a prefix, and
words that share a prefix share the same branch, so the prefix is stored once.

That layout makes the trie's signature operation — "is there any word starting with
this prefix?" — an O(L) walk down L characters, independent of how many words are
stored. It's the structure behind autocomplete, spell-checkers, and IP routing tables,
and its cost is measured in the length of the key, not the size of the dictionary.
"""


class TrieNode:
    __slots__ = ("children", "is_word")

    def __init__(self):
        self.children = {}       # char -> TrieNode
        self.is_word = False     # does a word END here (vs. just passing through)?


class Trie:
    def __init__(self):
        self.root = TrieNode()
        self._n = 0

    # region: insert
    def insert(self, word):
        """O(L) for a word of length L: walk down one character at a time, creating
        child nodes where the path doesn't exist yet. Words sharing a prefix reuse the
        same nodes — 'car' and 'card' share the first three."""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        if not node.is_word:
            node.is_word = True
            self._n += 1
    # endregion

    # region: search
    def search(self, word):
        """O(L): follow the characters. The word is present only if the whole path
        exists AND its final node is marked a word-end — 'car' being stored doesn't
        mean 'ca' is a word, even though its path exists."""
        node = self._find(word)
        return node is not None and node.is_word
    # endregion

    # region: starts_with
    def starts_with(self, prefix):
        """O(L): the trie's superpower. Is there ANY word with this prefix? Just check
        whether the path exists — you never look at the words themselves."""
        return self._find(prefix) is not None

    def _find(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node
    # endregion

    # region: words_with_prefix
    def words_with_prefix(self, prefix):
        """Autocomplete: walk to the prefix node, then collect every word-end below it.
        O(L + size of the subtree) — it visits only words that actually match, never the
        rest of the dictionary."""
        node = self._find(prefix)
        out = []
        if node is None:
            return out

        def dfs(n, suffix):
            if n.is_word:
                out.append(prefix + suffix)
            for ch, child in sorted(n.children.items()):
                dfs(child, suffix + ch)

        dfs(node, "")
        return out
    # endregion

    def __len__(self):
        return self._n

"""Python has no built-in trie; the third-party `pygtrie` is the ready-made option, and
a trie is really just nested dicts (`dict` of `dict` of …), which is how you'd hand-roll
one. The instructive counterpart, though, is the NAIVE way to answer a prefix query
without a trie: scan the whole word list and keep the ones that start with the prefix.
That's O(N·L) per query, against the trie's O(L + matches) — and the face-off shows the
trie pulling away as the dictionary grows.
"""


# region: scan_prefix
def words_with_prefix_scan(words, prefix):
    """The naive prefix query: check every word in the dictionary — O(N·L) per query,
    where a trie is O(L + number of matches) and never touches the non-matching words."""
    return sorted(w for w in words if w.startswith(prefix))
# endregion


# region: set_membership
def contains_scan(word_set, word):
    """Membership via a set — O(L) to hash the word, like the trie's search, but a set
    can't answer prefix queries at all without scanning."""
    return word in word_set
# endregion

Scratch vs library

This face-off isn't Python versus C — it's the right data structure versus the wrong one, and the trie wins by getting faster relative to the alternative as the problem grows. At 320000 words it answered prefix queries 8× quicker than scanning, and that multiple keeps climbing with the dictionary, because the scan is O(N·L) per query while the trie is O(L). This is the lesson the complexity chapter opened with, in its clearest form: the scan's constant factor is tiny (a C str.startswith in a comprehension), yet it still loses decisively, because a worse complexity class cannot be rescued by a better constant once N is large enough. Pick the structure whose cost doesn't grow with the thing that grows — here, the dictionary — and you win no matter how well-tuned the alternative is.

Where you'll actually meet it

Tries run every prefix feature you use. The autocomplete in your search bar, editor, and shell walks a trie of possible completions. Spell-checkers store their dictionaries as tries to suggest corrections by prefix. Every internet router forwards packets by longest-prefix match on a compressed trie of IP address ranges — arguably the most performance-critical trie in the world. Compilers and search engines tokenize text against tries of keywords and terms. Bioinformatics indexes genomes with tries (and their cousin, the suffix tree, two chapters on). And the T9 predictive text on old phones, and the swipe keyboards on new ones, are tries under the hood. Whenever the question is about the beginnings of strings, this is the structure.

Takeaways

A trie keys strings by their characters, sharing common prefixes down shared branches, so insert, search, and prefix queries all cost $O(L)$ in the key length and are independent of the dictionary size N — which is what makes autocomplete and "any word with this prefix?" essentially free. It pays for that with memory (a node per character), which compressed variants like radix trees reclaim, and it's only worth it when prefixes are genuinely your question; for plain membership, a hash set is leaner.

The trie is the first of the tree tier's specialized structures — a tree shaped for one kind of query. The next two chapters continue that theme with trees built for range queries over arrays: the segment tree and the Fenwick tree, which answer "what's the sum (or min, or max) of this range?" and "update this element" both in O(log n), where a plain array forces you to choose between fast queries and fast updates.