59The trie — a tree indexed by letters

In Chapter 58 we packed a whole tree into a flat array and let arithmetic replace the pointers. Now we go the other way, back to scattered nodes — but with a twist that sounds almost like a riddle. A trie stores each word not in a node but in the path to it. The word isn't kept in a box. It's spelled by the walk from the root, one letter per edge, and any two words that begin the same way share those first steps. Here's the plan. We'll build the prefix tree from its scattered heap nodes up, weigh what a single node really costs, and watch its lookup stay dead flat while the dictionary grows a thousandfold. The whole way through, we keep asking the one question that matters: if a hash map already finds any key in one shot, why would anyone walk a word letter by letter at all? By the end you'll read a word as a route, know exactly why finding cat takes three steps whether the trie holds ten words or ten million, and be able to do the one thing a hash map cannot — ask for every key that starts with cu.

01A word is a path, not a payload

Let's start with the one idea everything else hangs on, naming each piece as it lands. A trie — the name comes from retrieval, though most people say it "try" to keep it distinct from "tree" — is a tree whose edges are labelled with symbols; here, letters. Now watch where the letter goes, because that's the whole trick. A node holds two things, and — remarkably — not the letter: a children map that sends each next-symbol to the child it leads to, and a boolean end-of-word flag that says "a stored word finishes exactly here." The letter lives on the link, not in the node. So a key is just the sequence of edge-labels you cross from the root down to an end-flagged node. The root spells the empty string. Walk c, then a, then t, land on a node whose flag is true, and you have read the word cat straight off the edges.

The magic is what happens when two words agree at the start. cat and car share c-a, so they share those two nodes and only split at the third step. That's the defining move of the structure: a shared prefix is a shared path. Store a thousand words that begin auto… and the a-u-t-o spine exists exactly once, with a thousand routes fanning out past it.

Now the memory picture — this volume's obsession. Nowhere in RAM is there a tidy lattice of letters. On the heap a trie is a scatter of tiny node objects. Each one is a record of two fields: a reference to its children map (itself a hash table, the same one we built back in the hash-map chapter) and a one-byte-ish flag. The root is just a name holding a single 8-byte reference (Volume 1). Every edge is a key in some node's children dict, pointing at another scattered node. Follow the keys and you are the trie. The shape exists only as pointers, exactly as it did for the binary tree — only now each node branches by label, not by a fixed left or right.

How heavy is one node? Measure, don't guess. Give the class __slots__ (Volume 1) so its two fields pack straight into the object.

import sys

class TrieNode:
    __slots__ = ('children', 'is_end')   # pack the 2 fields INTO the object
    def __init__(self):
        self.children = {}                # a dict: letter -> child TrieNode
        self.is_end   = False             # does a stored word end here?

n = TrieNode()
print(sys.getsizeof(n))                    # 48  → node record itself
print(sys.getsizeof(n.children))           # 64  → its (empty) children dict

Line 4 is the shape of the whole structure: a node is a map plus a flag. Run on CPython 3.12.7, sys.getsizeof(n) returns 48 bytes for the node record, and the empty children dict it points at is another 64. So a bare node costs about 112 bytes before it holds a single child. That dict is the trie's whole personality — it's how one node branches into many. Hold that number: the next two sections are a fight over it.

Start with the thing it does faster in a way you can feel: its lookup cost doesn't depend on how much you've stored. Let's derive that from the layout. →

02Why lookup costs the word's length, not the dictionary's size

Reading a word out of a trie is a walk, and the walk writes itself. Stand on the root, and for each character of the key, follow the child link labelled with that character. If the link is missing, the word isn't stored — stop. If you run out of characters, check the end-flag on the node you're standing on. That's it.

def insert(root, word):
    cur = root
    for ch in word:                       # one step per character
        if ch not in cur.children:
            cur.children[ch] = TrieNode()  # carve a new path node when needed
        cur = cur.children[ch]            # descend the link labelled ch
    cur.is_end = True                     # plant the flag where the word ends

def contains(root, word):
    cur = root
    for ch in word:
        cur = cur.children.get(ch)        # follow the link, or None if absent
        if cur is None:
            return False                  # fell off the tree → not stored
    return cur.is_end                     # arrived → is a WORD only if flagged

Read contains as the cost model. The loop runs once per character of the key, and each pass does exactly one dict lookup and one pointer hop. So a key of length L costs L steps — the operation is O(L). Now look at what's not in that count: the number of words already stored, N, appears nowhere. Whether the trie holds ten words or ten million, cat is three links from the root and no more. The last line earns its keep. Arriving at a node isn't enough — ca is a real node on the way to cat, but it counts as a word only if its flag is set. The end-flag is what separates a prefix from a word.

I built tries of 1,000, 100,000, and 1,000,000 random 8-letter words and timed 200,000 lookups of the fixed word cat at each size. The exact nanoseconds are machine-dependent, so hedge them — but the shape is the point:

N=    1000: nodes=     6538   lookup('cat') ~ 163 ns
N=  100000: nodes=   507662   lookup('cat') ~ 160 ns
N= 1000000: nodes=  4381570   lookup('cat') ~ 161 ns   # 1000x the words, same time

The trie grew by a factor of a thousand — from 6,538 nodes to 4.4 million — and the lookup didn't move: ~161 ns, three hops, flat. That flatness is O(L) with no hidden N. Now for the honest comparison the scope demands. A hash map (the one we dissected in the hash-map chapter) is also O(L) in the key. Its hash function must read every one of the L characters to compute a bucket, and a match re-checks all L on the hit. So both structures touch all L characters — the "trie is O(L), dict is O(1)" line you'll hear is a half-truth. The real difference is how they touch them. The trie consumes the key one character at a time along a path, so it can quit at the first missing link, and every prefix it passes through is a real, addressable place. The hash map grinds the whole key into a single number and jumps to one bucket, so it has no idea that car lies on the road to card.

That flat, N-independent cost sounds like a free lunch. It isn't — you paid for it up front, in bytes. Time to open the children map and count. →

03The space bill: prefixes shared, alphabets paid

Here is where most people's intuition about tries is upside down. "It shares prefixes, so it must save memory," the story goes. Let's measure it instead of believing it. I stored 1,600 words that overlap heavily — roots like auto, inter, and under crossed with common stems and suffixes — and compared a dict-node trie against a plain Python set of the same strings.

1600 words · 15,600 characters if written out end to end
trie nodes ............ 3,523     # prefix sharing folded 12,078 char-slots away
trie total bytes ...... 676,224   # ≈ 423 bytes / word
set-of-str bytes ...... 212,488   # ≈ 133 bytes / word

Both halves of that are true, and both matter. Prefix sharing is real: 15,600 characters collapsed into 3,523 nodes — twelve thousand repeated character-positions simply vanished onto shared paths. And yet the trie weighs three times as much as the set. Why? Because every one of those 3,523 nodes drags a children dict behind it — that 64-plus-byte map from the last section — plus 48 more for the node object. You saved on character-slots and then paid it all back, with interest, in per-node overhead. The sharing bought you fewer boxes, but each box is expensive.

It gets worse in the textbook version. The classic trie doesn't use a dict per node — it uses a fixed array, one slot per possible symbol: 26 for lowercase letters, 256 for bytes. That array is the same size whether the node has one child or twenty-five.

So the trie is heavier and its lookup is no faster in Big-O than a hash. If that were the whole story, no one would build one. But there's a query it answers that a hash map cannot even attempt — and it's the reason you meet tries every single day. →

04The superpower: every word beneath a point

Ask a hash map "give me every key that starts with cu." It can't. A hash function deliberately scatters keys, so cup, cur, and cute land in unrelated buckets with nothing between them. The whole design goal is to destroy any relationship between similar keys. To answer the prefix question, it would have to scan all N keys and test each one: O(N).

A trie answers it structurally, because it never destroyed the relationship in the first place. Every word starting with cu lives in the subtree hanging below the cu node. So the query is two moves: walk to the prefix node (O(length of the prefix)), then collect every end-flag in the subtree below it. You visit only the words that match — nothing else in the trie is touched.

def starts_with(root, prefix):
    cur = root
    for ch in prefix:                     # 1) walk to the prefix node — O(len prefix)
        cur = cur.children.get(ch)
        if cur is None:
            return []                     # nothing in the trie starts this way
    out = []
    def collect(node, path):              # 2) gather every end-flag below it
        if node.is_end:
            out.append(path)
        for ch, child in node.children.items():
            collect(child, path + ch)
    collect(cur, prefix)
    return out

The first loop is the ordinary descent — reach the node that spells the prefix, or bail if the path dies. The nested collect is a plain tree walk, the same descent we wrote for the binary tree, rooted at that node. Whenever it meets an end-flag it records the word built up so far, and it only ever descends links that exist. Run on our small trie, starts_with(root, "ca") returned ['cat', 'car', 'card', 'care'] and starts_with(root, "do") returned ['do', 'dog'] — exactly the words on those paths, gathered without looking at a single unrelated key. On the 1,600-word trie, starts_with(root, "auto") found all 160 matches by touching only the auto subtree.

You've now seen the trie's soul: a prefix is a place. But its Big-O advantage hides a cost the machine charges at runtime that the exponent never shows — the same one every pointer structure pays. →

05The pointer tax, one hop per letter

Big-O counts steps; the machine bills by the cache line (Volume 3's memory hierarchy). And a trie is one of the most pointer-heavy structures in this book: every single character of a lookup is a dict probe followed by a jump to a fresh, unrelated heap address — the scattered 0x7f… nodes from the first diagram. The CPU's prefetcher, which makes a contiguous array fly by guessing the next address, is blind here: it cannot predict where the a-link of this node lands. So each letter risks a cache miss and a stall on RAM. Reading a 10-letter word can mean ten dependent misses in a row — each jump's address only known after the previous load returns. The O(L) is honest; the constant hidden inside it is large and set entirely by that scatter.

This is why serious trie implementations rarely look like the teaching version. The first fix is path compression: if a run of nodes each has exactly one child, they carry no branching decision, so merge them into one edge labelled with the whole substring. That's a radix tree (or Patricia trie) — the same structure the Linux kernel uses for IP routing and that databases use for index keys. The second fix is layout: pack the nodes into one contiguous array (a double-array trie) so that following a link is arithmetic into a block the prefetcher loves, not a jump to the unknown. Both attack the constant, not the O — because on this structure the constant is where the pain lives.

You now have the whole trie: a path per word, O(L) reads, a heavy per-node bill, and a prefix superpower no hash can match. The only skill left is the one that matters most — knowing, on sight, when this is the shape to reach for. →

06When to reach for a trie

Strip it to the trigger. A trie earns its keep when your keys are sequences — strings, IP addresses, DNA, sequences of moves — and you query them by prefix or by best-match, not just by exact equality. That second clause is the whole decision. If all you ever do is "is this exact key present?" and "give me its value," a hash map is lighter, simpler, and just as fast — use it. The moment the question becomes "what completes this?", "what's the longest stored key that's a prefix of this?", or "iterate everything under this branch in order," the hash map goes quiet and the trie is the answer, because it alone kept prefixes as structure.

That is the 1% move again, and by now it's a refrain across this whole volume: match the access pattern to the layout. The trie's access pattern is unmistakable once you can name it — keys that share heads, questioned by their heads. When a router asks "which of my routes is the longest prefix of this address," when a search box asks "what have people typed that starts like this," when a spell-checker asks "what real words are one edit from this path," they are all asking the same question, and the trie is the same answer: descend by symbol, and let the shared paths do the work. Knowing that on sight — before you write a line — is most of what "good at data structures" means. The code, as always, is the easy part that follows.

Next (chapter 60): a trie is still a tree — one path to every node, no cycles, strictly top-down. Tear off that last rule. Let any node point to any node, let paths loop back on themselves, and the tree opens into the most general shape in this book: the graph, where a friendship, a road map, a web link, and a git history are all the same two sets — nodes and edges — and the only real question left is how you store the tangle. →