59The trie — a tree indexed by letters

In Chapter 58 we packed a whole tree into a flat array and let arithmetic stand in for the pointers. Here 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. A word isn't kept in a box. It's spelled by the walk from the root, one letter per edge. Any two words that begin the same way share the very same first steps. Here's the plan. We'll build the prefix tree from its scattered heap nodes up, then weigh what a single node really costs. After that we'll watch its lookup stay dead flat while the dictionary grows a thousandfold. And the whole way through we keep asking the one thing 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. You'll know exactly why finding cat takes three steps whether the trie holds ten words or ten million. And you'll be able to do the one thing a hash map simply 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, and name each piece the moment it lands. A trie is a tree whose edges are labelled with symbols, and here those symbols are letters. The name comes from retrieval, though most people say it "try" to keep it distinct from "tree." Now watch where the letter goes, because it's the whole trick. A node holds two things, and remarkably not the letter. It holds a children map that sends a next-symbol to the child it leads to. And it holds 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 nothing but 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, and land on a node whose flag is true. Now you have read the word cat straight off the edges.

One honest note before we go further. The end-of-word flag as described gives you a set. It answers "is this word stored?" and nothing more. To get a real map, the kind where cat maps to 42, you make one small change. Instead of a boolean flag, the end node carries a value slot, empty for "not a word" and filled for "a word ends here, and here's its payload." Everything else in the chapter is identical. We'll keep using the boolean flag because it keeps the pictures clean. But keep in mind the flag is just the simplest possible value: present or not.

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. This is the defining move of the structure: a shared prefix is a shared path. Store a thousand words beginning auto… and the a-u-t-o spine exists exactly once, with a thousand routes fanning out past it.

So how does a word get in? Building the trie is the same walk, with one difference. When a link you need is missing, you create it instead of stopping. Insert cat into an empty trie and you carve three new nodes, one per letter, then set the end-flag on the last. Now insert car. You walk c, then a, and both links already exist, so you reuse them for free. Only at the third letter do the paths part. The t was there, the r is new, so you add a single node and flag it. Two words, and yet the c-a spine was paid for exactly once, four nodes in total. Step the build above and watch a shared node light up only when a new word truly needs a new letter.

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 a record of just two fields. The first is a reference to its children map, itself a hash table, the very same one we built back in the hash-map chapter. The second is a one-byte-ish flag, and that is the entire node. The root is nothing more than a name holding a single 8-byte reference (Volume 1), and every edge is a key in some node's children dict that points at another scattered node. Follow those keys down from the root and you are the trie. Notice that the shape exists only as pointers, exactly as it did for the binary tree. Only now each node branches by label, not by fixed left/right.

To make that concrete, look at what a single children dict actually holds. In the trie for {cat, car, card, care}, the shared node after c-a has a children dict of exactly {'t': …, 'r': …} — two entries, each a single-character key pointing at the next scattered node. The node after car holds {'d': …, 'e': …}, splitting toward card and care. So the keys of every children dict are single characters, never whole words. And the letters you read while walking are those dict keys, not anything stored inside the nodes. The node itself is almost empty. The relationships between nodes are the whole structure.

So how heavy is one node? The honest answer comes the only way we trust in this book. Measure, don't guess. We give the class __slots__ (Volume 1) so its two fields pack straight into the object rather than sprawling into a per-instance dict.

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. Ran on CPython 3.12.7, sys.getsizeof(n) returns 48 bytes for the node record itself. 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 children dict is the trie's whole personality, because it is how one node branches into many. Hold that number in your head, because the next two sections are a fight over it.

Let's put a real number on that. Take our little trie for {cat, car, card, care} and count the nodes it needs: a root, then c, then the shared ca, then one node each for the tails t, r, d, and e. That is 7 nodes in all, and every one carries its own children dict, so the skeleton alone costs about 7 × 112 = 784 bytes. Now count the actual data those four words hold: cat, car, card, care is just 14 characters. Fourteen bytes of letters, wrapped in the better part of a kilobyte of structure. That gap between the data and the scaffolding is the whole story of this chapter.

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 practically writes itself. You stand on the root, and for each character of the key you follow the child link labelled with that character. If the link you need is missing, then the word isn't stored — stop right there. And if you run out of characters, you check the end-flag on the node you're standing on. That is the whole algorithm.

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). 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's a word only if its flag is set. The end-flag is what separates a prefix from a word.

Let's walk cat through that loop once, by hand, so the count stops being abstract. Step one: we stand on the root and ask its children dict for c, find it, and hop to the c node. Step two: we ask that node for a, find it, and hop again to ca. Step three: we ask for t, find it, and land on the cat node. The key is now spent, so we read that node's end-flag, see it set, and answer yes. Three characters, three dict probes, three hops — L equals 3, and the size of the trie never once entered the arithmetic.

Notice a bonus the cost model hands you for free: a miss can be cheaper than a hit. Look up dog in our {cat, car, card, care} trie. Step one asks whether the root's children dict holds a d. It doesn't. The link is missing, so we stop after a single character, one dict probe, and we already know dog isn't stored. We never touched the other two letters. A hash map can't quit early like this. It must grind all three characters of dog into a bucket before it can even look. The trie fails fast the instant the path runs out.

To watch that claim survive contact with a real machine, I built three tries of 1,000, then 100,000, then 1,000,000 random 8-letter words. At each size I timed 200,000 lookups of the same fixed word cat. The exact nanoseconds are machine-dependent, so treat them loosely, because the shape of the numbers is the real 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 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 crucially, 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, 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 result are true, and both matter. Prefix sharing is real: 15,600 characters collapsed into just 3,523 nodes, so twelve thousand repeated character-positions simply vanished onto shared paths. And yet the trie still 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 that remains is expensive.

Push those two numbers together and the tax gets a size. Those 3,523 nodes at roughly 112 bytes each come to about 3,523 × 112 ≈ 385 KB of structure for 1,600 stored words. Divide it out and each word is hauling around about 245 bytes of trie, even though the word itself is only a handful of bytes of actual text. The per-node overhead, not the letters, is what you are really paying for.

So if a trie costs three times the memory of a set and touches the same L characters on a lookup, a fair question is: why does anyone use one? Here's the honest answer, and it reframes the whole chapter. You don't reach for a trie to save space or to beat a hash map at exact lookup. On those two scores the hash map wins. You reach for it for the one question the hash map physically cannot answer, every key beneath a prefix, and you pay the per-node overhead as the price of keeping that structure alive. The next section is that payoff, and it's the reason the trie exists at all.

And it gets worse in the textbook version. The classic trie doesn't hang a dict off every node; instead it uses a fixed array with one slot per possible symbol, which is 26 for lowercase letters or 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. That is the point: 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).

Make that O(N) concrete for a second, because the word “scan” hides how brutal it is. Suppose the hash map holds a million keys and you want the ones that start with cu. There is no shortcut here: you must pull out all 1,000,000 keys, test each one's first two characters, and throw away the millions that don't match. The map spread the keys on purpose, so being neighbours in the alphabet buys you nothing. The work scales with everything you stored, not with the handful you actually want.

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. It reaches the node that spells the prefix, or bails 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']. Those are 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, but 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 makes a contiguous array fly by guessing the next address, but here it is blind. 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, but 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.

Here's how much that first fix buys you. Insert the single word automobile into a plain trie and you get a 10-node chain, one node per letter, each dragging its own 112-byte children dict for a lone child it never shares. A radix tree looks at that chain, sees no branching decision anywhere along it, and collapses the whole run into one edge labelled automobile. Ten nodes become one, and nine dependent pointer-hops become zero. The letters that never fork were never worth a node.

That IP-routing mention deserves a concrete look, because it's the trie's other superpower: longest-prefix match. Say a router knows two routes, 10.0.0.0/8 ("anything starting 10") and 10.1.0.0/16 ("anything starting 10.1"), and a packet arrives for 10.1.9.4. The router walks the address down the trie and passes both end-flags on the way. The rule is simple: the deepest flag it reaches wins, because the deeper node matched more of the address. So 10.1.9.4 takes the /16 route, not the /8. No hash map can do this, since it would need an exact key. But the trie answers it in one descent, because every route that could match sits on the single path the address spells out.

And notice why that has to work, because it isn't luck. Every route that could possibly match an address is, by definition, a prefix of that address — 10 and 10.1 are both prefixes of 10.1.9.4. And every prefix of the address lies on the one downward path the address spells out, in strict order of length. So a single descent is guaranteed to pass every candidate route, shortest first, and the last flag it meets is the longest match. The structure can't miss a route, because a matching route has nowhere else to live.

INPUTfrom collections import defaultdict

END = "$"                                  # "a word ends here" - a key, not a flag

def add(trie, word):
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})     # read-or-create, in ONE lookup
    node[END] = True

def walk(trie, prefix):
    node = trie
    for ch in prefix:
        node = node.get(ch)
        if node is None:
            return None                    # the road ran out - fail fast
    return node

def completions(node, prefix=""):
    if node is None: return []
    out = [prefix] if END in node else []
    for ch, kid in node.items():
        if ch != END:
            out += completions(kid, prefix + ch)
    return out

trie = {}
for w in ["the", "this", "that", "there", "then", "top"]:
    add(trie, w)

print("the whole structure:")
print(" ", trie)
print("\nchildren of the 'th' node:", list(walk(trie, "th")))
print("completions('th') :", completions(walk(trie, "th"), "th"))
print("completions('the'):", completions(walk(trie, "the"), "the"))
print("completions('z')  :", completions(walk(trie, "z"), "z"))
print("'the' a word?     ", END in walk(trie, "the"))
print("'th'  a word?     ", END in walk(trie, "th"), " <- a real node, not a word")

Trie = lambda: defaultdict(Trie)           # the one-liner: a dict that conjures dicts
t2 = Trie()
for w in ["the", "this", "that"]:
    node = t2
    for ch in w: node = node[ch]
    node[END] = True
print("\ndefaultdict trie  :", completions(t2, ""))

OUTPUTthe whole structure:
  {'t': {'h': {'e': {'$': True, 'r': {'e': {'$': True}}, 'n': {'$': True}}, 'i': {'s': {'$': True}}, 'a': {'t': {'$': True}}}, 'o': {'p': {'$': True}}}}

children of the 'th' node: ['e', 'i', 'a']
completions('th') : ['the', 'there', 'then', 'this', 'that']
completions('the'): ['the', 'there', 'then']
completions('z')  : []
'the' a word?      True
'th'  a word?      False  <- a real node, not a word

defaultdict trie  : ['the', 'this', 'that']

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," then a hash map is lighter, simpler, and just as fast — use it. But the moment the question becomes "what completes this?", or "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. Now 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. A router asks "which of my routes is the longest prefix of this address." A search box asks "what have people typed that starts like this." 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.

import heapq
from collections import Counter

END = "$"          # the end node's payload: how many times you have typed this word

def add(trie, word, count):
    node = trie
    for ch in word:
        node = node.setdefault(ch, {})
    node[END] = node.get(END, 0) + count        # a VALUE, not a bare flag

def build(counts):
    trie = {}
    for word, c in counts.items():
        add(trie, word, c)
    return trie

def walk(trie, prefix):
    node = trie
    for ch in prefix:
        node = node.get(ch)
        if node is None:
            return None                         # no stored word starts this way
    return node

def collect(node, prefix, out):
    """Every (count, word) at or below this node."""
    if END in node:
        out.append((node[END], prefix))
    for ch, kid in node.items():
        if ch != END:
            collect(kid, prefix + ch, out)
    return out

def suggest(trie, prefix, k=3):
    node = walk(trie, prefix)                   # 1) O(len prefix) walk
    if node is None:
        return []
    hits = collect(node, prefix, [])            # 2) sweep only that subtree
    return [w for _, w in heapq.nlargest(k, hits)]   # 3) chapter 58's size-k heap

typed = Counter({"the": 900, "this": 240, "that": 610, "there": 180, "then": 150,
                 "they": 300, "top": 40, "to": 1200, "tomorrow": 55})
trie = build(typed)

for p in ("t", "th", "the", "to", "z", ""):
    print(f"  suggest({p!r:5}) -> {suggest(trie, p)}")

print("\nevery completion under 'th', with its count:")
for c, w in sorted(collect(walk(trie, "th"), "th", []), reverse=True):
    print(f"    {w:9} {c}")

print("\n  words stored           :", len(typed))
print("  completions under 'th' :", len(collect(walk(trie, 'th'), 'th', [])))
print("  is 'th' itself a word? :", END in walk(trie, "th"))
print("  suggest('zz')          :", suggest(trie, "zz"), "- one dead link, walk over")

# ---------------- OUTPUT, verbatim (CPython 3.12.7) ----------------
#   suggest('t'  ) -> ['to', 'the', 'that']
#   suggest('th' ) -> ['the', 'that', 'they']
#   suggest('the') -> ['the', 'they', 'there']
#   suggest('to' ) -> ['to', 'tomorrow', 'top']
#   suggest('z'  ) -> []
#   suggest(''   ) -> ['to', 'the', 'that']
#
# every completion under 'th', with its count:
#     the       900
#     that      610
#     they      300
#     this      240
#     there     180
#     then      150
#
#   words stored           : 9
#   completions under 'th' : 6
#   is 'th' itself a word? : False
#   suggest('zz')          : [] - one dead link, walk over

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. →