CodeLudo 🔥 Daily Guides

In a Trie, Lookup Cost Depends on the Word, Not on How Many Words

✓ numbers produced by the code on this page · Published 2026-08-20

Most lookup structures answer is this key present? A trie answers a bigger question at the same price: what could this key still become?

It manages that by storing words the way they are spelled — one node per character, with any words sharing a prefix sharing the nodes for it. The path from the root to a node spells something, and everything below that node is the set of words that begin with it.

Type a word, one letter at a time

The letters offered at each step are exactly the ones that could continue a real word.

Walk a prefix tree cost follows the key, not the pile

A trie stores words by their letters rather than as whole strings: one node per character, and any words sharing a prefix share the nodes for it. These 9 words — cab, car, card, care, cat, do, dog, done, dot — contain 29 characters in total, but the trie needs only 13 nodes, because ca is stored once and serves five words.

Walking down from the root spells a prefix, and everything below where you stop is the set of completions. Stopping at car leaves 3 words reachable (car, card, care); stopping at do leaves 4 (do, dog, done, dot). Note that do is both a complete word and the beginning of three longer ones, which is why a trie has to mark word endings separately rather than assuming they are the leaves.

The cost of a lookup is the length of the key — 2 choices at the first step, then one node per character — and that does not change as more words are added.

The green ring marks a node where a word ends. Notice that 'do' has one even though three longer words continue through it.

That is not an analogy for autocomplete — it is autocomplete. An autocomplete box holds a trie (or something with the same shape), keeps a pointer to the node for what you have typed, and moves it one step per keystroke. It never searches the word list. The subtree under the pointer is the suggestion list, already assembled.

Two things the picture shows that a definition does not

Word endings have to be marked. do is a complete word and also the first two letters of dog, done and dot. If a trie assumed that words end at the leaves, do would be unfindable. That is the single most common bug in a first trie implementation, and it is visible here as a node with a ring that also has children.

Sharing is not a vague benefit. The nine default words contain 29 characters between them. The trie needs 13 nodes, because ca is stored once and serves five words. That ratio improves as the word list grows and the prefixes overlap more, which is why tries are used for dictionaries, routing tables and IP prefix matching.

The cost claim, measured

Here is the property that makes a trie worth the pointers: finding a word takes one step per character in that word, and the number of stored words never enters into it.

python 
from itertools import product


def build(words):
    root = {}
    for word in words:
        node = root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True          # marks "a word ends here"
    return root


def count_nodes(node):
    return sum(1 + count_nodes(child) for ch, child in node.items() if ch != "$")


def steps_to_find(root, word):
    """Returns how many nodes were visited, or None if the word is not stored."""
    node, steps = root, 0
    for ch in word:
        if ch not in node:
            return None
        node = node[ch]
        steps += 1
    return steps if node.get("$") else None


def words_under(node, prefix=""):
    out = [prefix] if node.get("$") else []
    for ch, child in sorted((c, n) for c, n in node.items() if c != "$"):
        out += words_under(child, prefix + ch)
    return out


small = ["cab", "car", "card", "care", "cat", "do", "dog", "done", "dot"]
# Every 4-letter string over a 7-letter alphabet that INCLUDES the letters of "card", so the
# same lookup can be run against both tries and compared.
big = ["".join(p) for p in product("abcdert", repeat=4)]

print(f"{'word list':<12} {'words':>6} {'characters':>11} {'trie nodes':>11}   find 'card'")
for name, words in [("small", small), ("7^4 = all", big)]:
    root = build(words)
    chars = sum(len(w) for w in words)
    found = steps_to_find(root, "card")
    print(f"{name:<12} {len(words):>6} {chars:>11,} {count_nodes(root):>11,}   {found if found else 'not stored'}")

print()
root = build(small)
for prefix in ["c", "ca", "car", "do", "don"]:
    node = root
    for ch in prefix:
        node = node[ch]
    print(f"typing {prefix!r:6} leaves {len(words_under(node, prefix))} word(s) reachable: {', '.join(words_under(node, prefix))}")
Output 
word list     words  characters  trie nodes   find 'card'
small             9          29          13   4
7^4 = all      2401       9,604       2,800   4

typing 'c'    leaves 5 word(s) reachable: cab, car, card, care, cat
typing 'ca'   leaves 5 word(s) reachable: cab, car, card, care, cat
typing 'car'  leaves 3 word(s) reachable: car, card, care
typing 'do'   leaves 4 word(s) reachable: do, dog, done, dot
typing 'don'  leaves 1 word(s) reachable: done

Both tries find card in 4 steps. One holds 9 words; the other holds 2,401 — 267 times as many — and the lookup is not one step longer, because a trie never compares the key against other keys. It just spells it out.

The second block is the autocomplete behaviour as data. Typing c and then a narrows nothing, because every c word here continues with a; typing r cuts five candidates to three. Each keystroke is one pointer move, and the answer is whatever sits underneath.

Trie or hash table?

A hash table also finds a key in time that does not depend on the number of keys, and uses far less memory doing it. If exact lookup is all you need, use the hash table.

The trie earns its cost when you need the neighbourhood of a key: everything starting with this prefix, the longest stored prefix of this string, all keys in alphabetical order. A hash table scatters keys deliberately, so it can answer none of those without examining everything it holds. A trie keeps related keys adjacent by construction, which is the same trade a bad hash makes in reverse — structure you can exploit, versus spread you cannot.

What this page simplifies