Advanced Structures

Tries (prefix trees)

Character-by-character lookup for strings

~11 minLesson 19 of 25Written by Claude Opus 4.8

Every time your phone finishes a word before you do, something is walking a trie. It is a tree where edges are letters and the path from the root spells a word - so all the words that begin the same way share the same opening corridor and only fork where they truly differ. That one idea turns "find every word starting with car" from a scan of the whole dictionary into a three-step walk that hands you a subtree. In this lesson you will type into a live trie and watch the matching path - and the candidate list - update on every keystroke.

One shared spine of letters

Picture cat, car, card, care, cart. They all begin c → a, so a trie stores that stem once. After the a the paths split: one branch to t (that's cat), another to r, and below r three more forks for card, care, cart. Nothing is duplicated. The word "trie" comes from retrieval - and it's the shape of retrieval itself: to look something up, you spell it.

One edge per character, plus a flag

A trie node holds a small map from the next character to a child node - nothing more. To find or store a key you start at the root (which represents the empty string) and follow one edge per character. Two subtleties make it work:

The root is empty. It carries no letter; it is just the shared starting point every word walks out from.
End-of-word markers. Because car is a prefix of card, the path for card passes straight through the r node. So each node carries a boolean: "a complete word ends here." Without it you couldn't tell a real word from a mere waypoint.

Cost tracks key length, not dataset size

Every operation walks the trie one character at a time, so the work is proportional to the length $L$ of the key - and is completely independent of how many keys $n$ are already stored:

insert (k ey) = search (k ey) = hasPrefix (p) = O (L) .

A balanced BST spends $O (lo g n)$ comparisons and each comparison may re-scan the whole key; a hash table hashes the whole key too. A trie instead does one cheap branch per character - and, uniquely, gives you every completion of a prefix essentially for free, because they all sit in a single subtree:

listAll (p r e f i x) = O (walk to the node L + total length of matches m) .

Autocomplete you can feel

Type a prefix into the search box and watch the path from the root light up one node per keystroke, while every word living in the subtree below drops into the completions panel. Click a completion to drill in. Then add a word of your own and watch the branch grow - reused characters glow amber (no duplication), brand-new ones glow green.

Live autocomplete trie type - complete - insert & reuse

autocomplete:matches 0

prefix pathprefix endcompletions belowreused (insert)new (insert)end of word

completions

Type a prefix above - the matching path lights up and the words below it appear.

add word:quick add:

words 0nodes 0prefix-sharing saves 0 letters

A prefix query is navigation, then a subtree

Answering "which words start with car?" is two moves: walk the three characters to land on the r node in

O (L)

, then collect every end-of-word marker in the subtree beneath it. Those completions were never searched for - they were simply already gathered together by the structure. That is why autocomplete, spell-checkers, IP routing tables, and T9 keypads all reach for a trie: the prefix is the address of its own results.

Speed has a price: pointers everywhere

A trie trades memory for prefix power. Each stored character becomes its own node with a child slot, so in the worst case a trie holds on the order of

O (n \cdot L \cdot ∣Σ∣)

pointers, where

∣Σ∣

is the alphabet size - a lot of near-empty maps. Shared prefixes claw much of that back (watch the "letters saved" readout climb as you add words), and a radix / compressed trie squeezes each run of single-child nodes into one edge. But if your keys share few prefixes, a plain hash table is smaller and just as fast for exact lookups - a trie earns its keep precisely when you need ordered or prefix queries.

The insert, in a handful of lines

Both insert and prefix-search fall straight out of the definition - walk character by character, creating a child only when one doesn't already exist, and mark the final node:

class Node:
    def __init__(self):
        self.kids = {}                    # char -> Node
        self.end  = False               # does a word end here?

def insert(root, word):
    node = root
    for ch in word:
        if ch not in node.kids:         # no branch for this letter yet?
            node.kids[ch] = Node()      # grow one (existing letters are REUSED)
        node = node.kids[ch]              # step down the shared path
    node.end = True                      # flag the last node end-of-word

def starts_with(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.kids:
            return []                    # path breaks -> no such prefix
        node = node.kids[ch]
    return collect(node, prefix)      # DFS the subtree for completions

Check yourself

What determines how long it takes to search a trie for a key?

In a trie, how are two words that share a common prefix stored?

Recall: what makes a trie's lookup independent of how many keys it stores - and why is an end-of-word marker necessary?

Recall the loop invariant. Try to state it, then check.

Lock it in

A trie is a tree whose edges are letters: words sharing a prefix share one path and fork only where they differ, so the common stem is stored exactly once.
Every operation walks one edge per character, so insert, search, and prefix queries cost $O (L)$ in the key length - independent of how many keys $n$ are stored.
The root is empty and each node carries an end-of-word flag; without it you cannot tell a stored word from a mid-path waypoint like car inside card.
A prefix query is navigation then a subtree, which is why autocomplete and routing tables reach for tries; the price is many pointers, clawed back by shared prefixes and radix compression.

Primary source

The canonical treatment is the tries chapter of the Sedgewick & Wayne Algorithms booksite (Princeton), which develops R-way tries and ternary search tries with full code and cost analysis. To watch inserts, searches, and prefix walks animate node by node, use the USF Data Structure Visualizations (David Galles), which includes an interactive trie alongside its BST and balanced-tree animations.

Ask your teacher

Curious how a radix trie compresses those long single-child chains, or how deletion cleans up dead branches? Ask me and we'll trace one. The bridge to the LLM path is direct: the BPE tokenizer from the language-modeling lessons keeps its vocabulary in a trie/prefix structure and, as text streams in character by character, walks that trie to match the longest token available - turning raw characters into token ids in near-constant time. The same "spell it to find it" walk you just did powers the first step of every prompt - the bridge traced in tries and hash maps to BPE tokenization in the LLM course.