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

A plain hash map does not directly answer “give me every key that starts with pre.” A trie walks the prefix, then traverses the matching subtree, so enumeration costs O(prefix length + visited nodes + output size). Tries are useful for autocomplete, dictionary prefixes, and longest-prefix routing, but sorted string structures and dedicated prefix indexes are alternatives.

A trie stores strings as character paths, sharing prefixes. Lookup/insert is O(key length), independent of the number of keys. Its strength is direct prefix traversal, which a plain hash map does not provide. Enumeration still pays for visited nodes and output; consider tries or other prefix indexes 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 length + visited nodes + output size) 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