Trie Pattern: Prefix Search Questions and the Standard Implementation

TL;DR: A trie stores strings one character per node, so every path down from the root spells a prefix and words that share a prefix share a path. That single property makes "does anything start with this?" cost the length of the prefix, no matter whether the dictionary holds ten words or ten million. Autocomplete, wildcard dictionary search, and finding every dictionary word hidden in a grid all reduce to walking that structure. The implementation is about twenty lines, and one boolean flag on each node is what separates a correct trie from a broken one.

This is the thirteenth deep dive in our pattern series (the full map lives in the hub), following union-find. Like union-find, a trie is a data structure rather than a traversal, and it belongs to the same group of patterns that candidates either know cold or do not know at all. The good news is that there is very little to learn: one class, one flag, and one clear rule about when a plain hash set is the better answer.

The tell: how to recognize a trie problem

Suspect this pattern when the question is about prefixes, not whole strings:

• "starts with", "prefix", "autocomplete", "type-ahead"
• "search a dictionary of words" repeatedly
• "replace words with their root form"
• "longest word built one character at a time from other words"
• "add and search words" with a wildcard character
• "find all words in a grid" (the hard one)

The signal to weigh most heavily is repeated prefix queries against a fixed set of words. A single lookup does not justify building anything. Many lookups, especially partial ones, is where the structure pays for itself.

The one insight the whole pattern rests on

Here is the sentence that is the pattern: the shared prefix is stored once, so lookup cost depends on the length of the word, not on how many words you stored.

Every node is a position in a string. Its children are the characters that can legally come next. Walking from the root, one node per character, either succeeds and lands you somewhere, or fails at the first character that has no matching child. The dictionary could hold a million words and the walk for a five-character prefix still touches five nodes.

That is the trade you are making. A trie costs more memory than a hash set, because a node exists for every distinct prefix, and it buys the ability to ask questions a hash set cannot answer at all: what comes next, what starts with this, what words live under this point.

The template

Two small classes, and you should be able to write them from memory:

class TrieNode:
    def __init__(self):
        self.children = {}          # character -> TrieNode
        self.is_word = False        # True if a word ends exactly here


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

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

    def _walk(self, prefix):
        """Return the node reached by prefix, or None if the path breaks."""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

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

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

is_word is the flag that makes the structure correct. Without it, search and starts_with are the same function, and inserting "apple" would make "app" report as a stored word. The node for the second p in "apple" exists either way, so the only thing distinguishing a real word from a passing prefix is that boolean. Whenever a trie solution returns true too often, this is the reason.

Note that search and starts_with are the same walk, read at a different moment. That is worth saying out loud, because it shows you built one primitive rather than two.

On the children container: a dictionary works for any alphabet and costs a hash per step. A fixed array of 26 slots is faster and more compact when the input is guaranteed lowercase English. Either is fine; naming the trade is what earns the point.

Complexity: insert and search are both O(L) for a word of length L. Space is O(total characters across all words) in the worst case, which is the honest cost of the structure.

The compass: trie or hash set?

Interviewers reach for this comparison often, because a trie is frequently the wrong answer offered confidently.

• Exact lookups only. A hash set gives O(1) membership and takes one line. If the question never asks about partial words, a trie is strictly more code for strictly less speed.
• Prefix questions. Only a trie answers "what starts with this" without scanning every word.
• Enumerate everything under a prefix. A trie walks down and collects; a hash set has no notion of "under".
• Many words checked against one text, or against a grid. A trie lets you check all words at once during a single traversal, which is the entire reason Word Search II is tractable.

The short version: a hash set answers "is this word here", a trie answers "what could come next". Choose on that, and say why.

Want the whole family taught in order? The trie chapter of Grokking the Coding Interview builds from the basic implementation through wildcard search and Word Search II with worked traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Implement Trie (Prefix Tree): the template, asked directly. Know it cold.
• Replace Words: walk each word down the trie and stop at the first node where is_word is true. A three-line change to _walk.
• Longest Word in Dictionary: only words whose every prefix is also a word qualify, which is a natural fit for the structure and a good test of whether you understand is_word.
• Design Add and Search Words Data Structure: the . wildcard means that at that position you cannot follow one child, you must try all of them. Search becomes a small recursion over children rather than a loop. This is the standard step up from the template.
• Word Search II: the reason the pattern is worth learning. Build one trie from the whole word list, then run a single grid traversal carrying a trie node alongside your position. A cell only continues the search if the character exists as a child. Without the trie you run one grid search per word, which is far too slow.
• Maximum XOR of Two Numbers in an Array (stretch): a trie over the bits of each number rather than characters. Walk each number down the tree preferring the opposite bit at every step, greedily building the largest possible XOR. It looks like a different problem and it is the same structure.

The three mistakes that sink candidates

1. Omitting is_word. The most common trie bug. Every prefix reports as a stored word, and the failure only shows up on inputs where a prefix of one word is not itself a word.

2. Not pruning in Word Search II. After a word is found, remove it from the trie or mark it collected, otherwise the same word gets reported repeatedly. Better still, delete nodes that no longer lead to any word so the grid search stops going down dead paths. Solutions that time out on this problem almost always skipped the pruning, not the trie.

3. Building a trie when a hash set was asked for. Reaching for the heavier structure on a problem that only needs exact membership reads as pattern-matching rather than thinking. State the comparison, then choose.

Practice ladder

In order, each rung adding one wrinkle.

1. Implement Trie (Prefix Tree) (M): the template from memory.
2. Longest Common Prefix (E): solvable without a trie, which is exactly why it is here. Notice the boundary.
3. Replace Words (M): stop the walk at the first complete word.
4. Longest Word in Dictionary (M): every prefix must also be a word.
5. Design Add and Search Words Data Structure (M): the wildcard turns the loop into a recursion.
6. Word Search II (H): one trie, one grid traversal, with pruning.
7. Stretch: Maximum XOR of Two Numbers in an Array (M): the same structure over bits.

Then write the tell in your own words ("I should suspect a trie when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One structure (a node per character, children keyed by the next character), one flag that decides correctness (is_word), one cost model worth stating (O(length), independent of dictionary size), one boundary (a hash set wins when only exact lookups are needed), and one problem that justifies the whole pattern (Word Search II, where a single trie replaces one search per word). The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: Cyclic Sort, where the numbers tell you their own index.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential trie problems in its 6-week plan.

FAQs

What is a trie in simple terms? A tree where each node represents one character and each path from the root spells a prefix. Words that begin the same way share the same path, so storing "car" and "card" uses one chain of nodes rather than two separate strings.

Why does a trie need an is_word flag? Because the path for a short word also exists inside a longer one. After inserting "apple", the nodes for "a", "ap", and "app" all exist, and only the flag records that "apple" was actually stored while "app" was not. Without it, every prefix falsely reports as a word.

When is a hash set better than a trie? Whenever the question only asks whether an exact word is present. A hash set gives O(1) lookup with far less memory and one line of code. A trie earns its cost only when you need prefix queries, wildcard matching, or the ability to enumerate everything below a point.

How does a trie make Word Search II fast? It lets you search for every word at once. You build one trie from the word list, then traverse the grid a single time while walking the trie in step with your position. A cell is only worth exploring if its character exists as a child of the current node, which prunes most of the search immediately.

Is the trie pattern asked at FAANG companies? Yes. Implement Trie and Design Add and Search Words are common screens, Word Search II is a recurring hard at Google and Amazon, and prefix-search questions appear often on teams that work on search or autocomplete features.