Tries: When Prefix Is the Question

A hash set can tell you instantly whether the exact word “apple” is stored. What it can’t tell you, without scanning every key, is whether any stored word begins with “app” — and that question, “is this a prefix of something I know,” is the one a trie is built to answer. A trie is a tree where each edge is a single character, so the path from the root to a node spells a prefix, and words that share a beginning share the nodes for it. Looking up a word, or a prefix, costs only its length — completely independent of how many words the trie holds.

A node is almost nothing

A trie node holds two fields: a map from the next character to a child node, and a flag marking whether a word ends here. Insert walks the word, creating children as needed; search and prefix-check walk the same way and differ only in what they check at the end.

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}

void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        node = node.children.computeIfAbsent(c, k -> new TrieNode());
    }
    node.isEnd = true;                          // a word ends at this node
}

boolean startsWith(String prefix) {
    TrieNode node = root;
    for (char c : prefix.toCharArray()) {
        node = node.children.get(c);
        if (node == null) return false;         // fell off the tree — no such prefix
    }
    return true;                                // full search adds: && node.isEnd
}

Implement Trie is exactly this — insert, search (the same walk ending in node.isEnd), and startsWith (ending in “we didn’t fall off”). Everything else in the category is a variation on that walk.

When a wildcard fans the walk out

Design Add and Search Words adds a . that matches any single letter, and it turns the straight walk into a small branching search. At a normal character you follow the one matching child; at a . you have to try every child and succeed if any of them leads to a match. That’s a depth-first fan-out — the same backtracking shape as the grid problems, but over the trie’s children instead of a board. A word full of dots degrades toward scanning the subtree, but a single concrete letter anywhere still prunes hard.

Why grid word-search reaches for a trie

Word Search II is the payoff problem: find which of many words appear in a letter grid. Searching the grid once per word is hopeless, so you flip it — build a trie of all the words, then run a single trie-guided DFS out of each cell instead of one full search per word. It’s still a backtracking walk that can branch and revisit, but the trie is shared across every word and prunes hard: the instant the letters you’ve spelled aren’t a prefix of any word, there’s no child to follow and you abandon that path immediately. It’s a backtracking grid walk and a tree at the same time — the board supplies the moves, the trie supplies the “is this still worth it.”

You have queried a prefix tree today

Prefix lookup is quietly everywhere. Many autocomplete and typeahead boxes walk a trie to offer completions of what you’ve typed (others reach for search indexes or finite-state transducers). A classic user is routing: an IP forwarding table does longest-prefix match to pick the next hop, and a compressed radix trie is one common way to store it so software can match a destination address against thousands of prefixes quickly — though high-end routers often push this into TCAM hardware instead. A URL router in a web framework does the same prefix matching over path segments. The interview trie is the toy model of the structure that decides where real packets go.

What it costs

Insert, search, and startsWith are each $O(L)$ in the length of the word — never in the number of words stored, which is the whole reason to pay for the extra nodes. Space is the catch: in the worst case a trie holds a node per character, though shared prefixes claw much of that back, and the child map’s overhead is why a fixed TrieNode[26] array is common when the alphabet is small and known. The trade is more memory in exchange for prefix queries that don’t slow down as the dictionary grows — worth it exactly when prefixes are what you ask about. My own rule is to default to a plain hash map and only switch to a trie once “starts with” or “autocomplete” is actually in the requirements; the prefix queries have to be real, not hypothetical, to earn the extra nodes.

Prefix in, prefix out

The tell for this category is any question phrased about beginnings rather than whole values — “starts with,” “shares a prefix,” “which of these words appear as we scan.” A hash map is usually simpler and lighter for exact membership — hashing a string is $O(L)$, the same order as walking a trie — so a trie only earns its extra nodes when prefixes are the actual query. When they are, three problems drop out of one small structure: store words as shared paths, walk a path to answer a lookup, and let the absence of a next edge tell you when to stop.

References

• NeetCode 150 — Tries — all three prefix-tree problems.