Tries: The Tree That Spells

"A hash map can tell you if 'pippa' is in your set. A trie can tell you every word that starts with 'pip' — and that one extra power runs every autocomplete you've ever used."

A Tree Built From Letters

A trie (prefix tree) stores strings by their characters: each edge is one character, and each path from the root spells out a prefix. Words that share a prefix share the same path until they diverge — "cat," "car," and "card" all walk c→a→ together, then split. A node is marked as the end of a real word so you can tell "car" (a word) from "ca" (just a prefix on the way to one).

The Costs Are Different in a Useful Way

Insert and lookup walk one edge per character, so they're O(L) where L is the length of the key — and crucially, that's independent of how many words the trie holds. A trie with ten words and a trie with ten million words both look up a 5-letter word in 5 steps. (A hash map is also fast here, but its cost depends on hashing the whole key; the trie's depends only on key length.)

The Killer Feature: Prefix Queries

Here's what a hash map simply cannot do: answer "give me every key that starts with pre." In a trie, you walk to the node at the end of pre (O(prefix length)), then everything in the subtree below it is a word with that prefix — collect them in O(number of results). This is exactly what powers autocomplete (suggest completions as you type), spell-check, dictionary lookups, and even IP routing (routers do longest-prefix matching on address bits). When the query is about prefixes, the trie is the structure, the same way the BST is the structure when the query is about order.

A trie stores strings as character paths, sharing prefixes. Lookup/insert is O(key length), independent of the number of keys. Its unique power is prefix queries — 'all words starting with X' — which hash maps can't do. Use it for autocomplete, spell-check, and routing.

The Trade-Off

Tries aren't free. Each node carries overhead (a map of child characters), so for a small set of unrelated strings a trie can use more memory than a plain hash set — the savings only materialize when many keys share prefixes. And a hash set still wins for pure exact-membership with no prefix needs. As always: the trie earns its place precisely when the query shape is "prefix," and is overkill when it isn't. Right structure, right query.

Pippa's Confession

I tried to build autocomplete with a hash set and a loop that checked key.startswith(prefix) for every key — O(n) per keystroke, and it lagged on a big dictionary. Dad drew a trie and the lag vanished: walk to the prefix node once, read the subtree. It reframed structures for me yet again — the hash set answered the wrong question. It's fabulous at "is this exact word here?" and helpless at "what continues this?" The query shape chooses the structure.

Code

A trie with insert, search, and prefix query·python

class Trie:
    def __init__(self):
        self.root = {}                  # nested dicts; '$' marks end-of-word

    def insert(self, word):             # O(len(word))
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})   # walk/create one edge per char
        node["$"] = True                # mark a real word ends here

    def search(self, word):             # O(len(word)) exact-word lookup
        node = self.root
        for ch in word:
            if ch not in node: return False
            node = node[ch]
        return "$" in node

    def starts_with(self, prefix):      # the killer feature hash maps lack
        node = self.root
        for ch in prefix:
            if ch not in node: return []
            node = node[ch]
        words = []                      # collect every word in this subtree
        def collect(n, path):
            if "$" in n: words.append(prefix + path)
            for ch, child in n.items():
                if ch != "$": collect(child, path + ch)
        collect(node, "")
        return words

t = Trie()
for w in ["cat", "car", "card", "dog"]:
    t.insert(w)
print(t.search("car"))          # True
print(t.search("ca"))           # False — a prefix, not a stored word
print(t.starts_with("car"))     # ['car', 'card'] — prefix query, the trie's gift

Exercise

Insert 'to', 'tea', 'ted', 'ten', 'in', 'inn' into a trie and sketch the shared structure. Which prefix path is shared by 'tea', 'ted', and 'ten'? Then explain why answering 'all words starting with te' is O(prefix + results) and not O(total words stored).

Hint

'tea','ted','ten' share the t→e path, then split at the third letter. 'all words starting with te' walks the 2-char path to the 'te' node, then only explores that subtree — it never touches 'to', 'in', or 'inn', so cost depends on the prefix and the matches, not the whole trie.

A Tree Built From Letters

The Costs Are Different in a Useful Way

The Killer Feature: Prefix Queries

The Trade-Off

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0