Tries: Sharing Prefixes

Words as paths

A trie (also called a prefix tree) is a tree where each edge carries one character, so every root-to-node path spells out a prefix. Words that share a beginning share a path — store "car", "card", and "cat" and the c → a section exists exactly once:

root
 └─ c
     └─ a
         ├─ r ●        "car" ends here
         │   └─ d ●    "card" ends here
         └─ t ●        "cat" ends here

Each node holds two things:

• A children map — from a character to the child node for that character.
• An end-of-word flag (call it isWord) — marked ● above.

The flag is not optional. In the tree above, the node for "ca" exists (it's on the way to three words) but "ca" is not itself a stored word. Without the flag you could not tell "car" (a real word and a prefix of card) apart from "ca" (only a prefix). A prefix existing is not the same as a word existing — forgetting this is the most common trie bug.

The three core operations

class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
        cur.is_word = True          # the flag, not just the path

    def search(self, word):         # exact word membership
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):  # any word with this prefix?
        return self._walk(prefix) is not None

    def _walk(self, s):
        cur = self.root
        for ch in s:
            if ch not in cur.children:
                return None
            cur = cur.children[ch]
        return cur

Notice that search and starts_with are the same walk — the only difference is whether you demand the flag at the end.

Why not just a hash set?

Every operation above costs O(L), where L is the length of the word being processed — completely independent of how many words are stored. Checking "does anything start with pre-" costs three steps whether the dictionary holds ten words or ten million. Compare against a hash set of words:

For exact membership, the hash set is fine — simpler, and equally fast. The trie earns its keep the moment the question involves prefixes: autocomplete, spell-check suggestions, "streaming characters" problems. (You could make a hash set answer prefix queries by inserting every prefix of every word, but that multiplies memory by average word length and still can't enumerate completions.)

Space is the trie's cost: one node per unique character-position, plus per-node child storage. Two implementation choices: a fixed 26-slot array per node (fast, but 26 pointers even when a node has one child — memory balloons on large dictionaries) or a hash map of children (pay only for children that exist). Default to the map; mention the array as the constant-factor optimization.

Wildcards: when the walk must branch

Design Add and Search Words adds one twist: the search string may contain ., which matches any single character. A plain walk breaks — at a . there is no single edge to follow. The fix is a depth-first search (DFS): at a literal character, follow that one edge as before; at a ., try every child and succeed if any branch works.

def search(self, word):
    def dfs(node, i):
        if i == len(word):
            return node.is_word
        ch = word[i]
        if ch == ".":
            return any(dfs(child, i + 1) for child in node.children.values())
        if ch not in node.children:
            return False
        return dfs(node.children[ch], i + 1)
    return dfs(self.root, 0)

Cost: still O(L) for wildcard-free queries; with dots, the walk can fan out toward O(26^d) for d dots — which is why such problems keep patterns short.

The heavyweight application: trie-pruned grid search

Word Search II gives a letter grid and a list of words; find every word traceable through adjacent cells. Searching the grid once per word repeats enormous work — "cat" and "card" retrace the same c → a path.

Instead, build one trie of all target words, then run a single DFS from each grid cell, moving through the grid and the trie in lockstep: step onto a neighboring cell only if the current trie node has a child for that letter. The trie becomes a pruning oracle:

• No child for the letter → no target word continues this way — abandon the entire branch immediately.
• Node has is_word → record that word (and unset the flag so it isn't reported twice).
• After a word is found, snip dead leaves (nodes with no children and no word) so exhausted paths stop future walks even earlier.

That pruning is the difference between passing and timing out: without it you're doing W independent grid searches; with it, one search shares all prefix work and kills hopeless directions after a single letter.

Recognition signals and pitfalls

Reach for a trie when you see: "prefix", "starts with", "autocomplete", a dictionary of words queried repeatedly, wildcard word matching, or many words searched in one grid.

The classic mistakes:

1. No is_word flag — prefix existence gets mistaken for word existence.
2. Treating . as one step — wildcards require branching DFS over all children.
3. Word Search II without pruning — remove found words and dead leaves, or TLE.
4. 26-array children on big inputs — a child map avoids paying for absent letters.