Trie
- Implement a trie with insert, search, and startsWith from scratch, understanding that search and startsWith differ by exactly one boolean check
- Recognize when a trie beats a HashSet: any problem involving prefix operations, simultaneous multi-word search, or lexicographic ordering
- Combine trie traversal with board DFS for Word Search II, using the trie as a pruning mechanism that searches all words simultaneously in one pass
- Handle wildcard matching by branching to all children on '.', understanding the recursive structure this requires
- Recognize when a trie is the wrong choice and a HashMap or sorted structure is sufficient
- Rebuild the trie pattern from the core question: does this problem need shared-prefix structure?
A trie stores strings as paths through a tree where shared prefixes share nodes. Insert and search are both O(L) where L is the word length. A HashMap also takes O(L) for string lookup once you account for the cost of hashing the key. The trie gives you prefix operations on top of that. When a problem says "find all words starting with," "shortest root prefix," or "search a board for multiple words," the trie is the right data structure because it lets you navigate to a prefix and operate on every word below it without scanning unrelated entries.
What a Trie Actually Does
Consider checking whether any word in a dictionary starts with "app." With a list or a HashSet, you have to scan every entry and test each one. With 100,000 words, that is 100,000 prefix comparisons. A trie navigates directly to the node for "app" in three steps, regardless of how many words exist. Everything below that node shares the prefix.
The same principle applies at a larger scale. In Word Search II, the naive approach runs a separate DFS for each target word. With k words on an m x n board, that is k independent searches. A trie holds all k words at once, so a single DFS from each cell can check all words simultaneously. Whenever the current board path does not match any trie prefix, the DFS stops that branch immediately.
A trie is a tree where each node represents a character and each path from root to a marked node represents a stored word. The root is empty. The first level holds first characters. The second level holds second characters, and so on. Words that share a prefix follow the same path until they diverge.
Building a Trie
Start with an empty root node. Each path from root to a leaf spells out a word.
The root represents the empty string. Every word starts its traversal here.
The fundamental building block is the TrieNode. Each node needs two things: a collection of children (mapping characters to child nodes) and a flag indicating whether this node marks the end of a complete word.
End Markers: Prefix Search vs Word Search
Every trie node represents a prefix, but not every prefix was inserted as a complete word. After inserting "apple," the trie contains nodes for "a," "ap," "app," "appl," and "apple." Only the node at "apple" has is_end = True. The other nodes exist because they are part of the path, not because someone inserted "app" as a word.
This is the single most important distinction in trie problems. search("app") must return False when only "apple" was inserted, because the node at "app" has is_end = False. startsWith("app") returns True because the path exists. The only difference between search and startsWith is one boolean check at the final node.
search that returns True for any prefix. If you insert "apple" and then call search("app"), you must return False because "app" was never inserted. The only difference between search and startsWith is the is_end check. Forgetting it means every prefix of every inserted word gets reported as found.First Walkthrough
Start with an empty trie (just a root node with no children). Insert three words: "app," "apple," and "apt."
Insert "app": The root has no children. Create a child node for "a." From "a," create a child for "p." From that "p," create another child for the second "p." Mark this final "p" node with is_end = True. The trie now has the path root → a → p → p(end).
Insert "apple": Start at root. "a" already exists, follow it. First "p" already exists, follow it. Second "p" already exists, follow it. Now create "l" as a new child. Create "e" as a child of "l." Mark "e" with is_end = True. The first three characters reused existing nodes. Only two new nodes were created.
Insert "apt": Start at root. "a" exists, follow it. First "p" exists, follow it. This "p" node has a child for the second "p" (from "app") but no child for "t." Create "t." Mark "t" with is_end = True. The path diverged at the first "p" node.
Now query: search("app") follows a, p, p and checks is_end. It is True (we inserted "app"), so return True. search("ap") follows a, p and checks is_end. It is False (no word "ap" was inserted), so return False. startsWith("ap") follows a, p and confirms the path exists. Return True, because "app," "apple," and "apt" all start with "ap."
Insert, Search, and StartsWith
These three operations are the foundation for every trie interview problem. The Implement Trie problem asks you to build exactly this. Every operation follows the same pattern: walk the tree one character at a time.
Insert / Search / StartsWith
Insert "apple": start at root, create nodes for each character.
insert() creates new child nodes for characters not already in the trie.
_find (or _traverse) helper. Both search and startsWith use it. Search adds one extra check on is_end. This avoids code duplication and shows the interviewer you think about structure.Wildcard Search: Branching on Dot
Design Add and Search Words Data Structure adds one twist to the basic trie: a "." character that matches any single letter. The insert operation is unchanged. The search operation must branch when it encounters a dot, because the dot could match any child in the current node. This converts the single-path traversal into a DFS that tries every child and returns True if any branch completes the word.
Wildcard Search: "c.t"
Trie contains: "cat", "cut", "cot", "car". Search for pattern "c.t" where "." matches any character.
The dot wildcard means we must check ALL children at that position, not just one.
When the current character is a specific letter, follow that one child. When the current character is ".", you cannot follow a single path. Instead, try every existing child and return True if any branch succeeds. This makes the search recursive.
Word Search II: Trie as Pruning Mechanism
Word Search II is the hardest and most important trie problem. Given an m x n board of characters and a list of words, find all words that can be formed by sequentially adjacent cells (horizontal or vertical). Each cell can be used at most once per word.
The naive approach: for each word, run a DFS on every cell. If there are k words, this is k separate board-DFS operations. The trie approach: insert all words into a trie, then run a single DFS from each cell, using the trie to prune branches that cannot lead to any word.
Word Search II: Board + Trie
Board and trie for words ["oath", "eat"]. DFS from each cell, guided by the trie pointer.
The trie lets a single DFS check all target words at once instead of one word at a time.
if not child.children: del node.children[char] is the optimization that prevents TLE. After exploring a node, if it has no remaining children (all words through it have been found), remove it from the trie. This progressively shrinks the trie as words are found, preventing redundant explorations. Without this optimization, large inputs with many words will TLE. Interviewers often ask specifically about this optimization.Autocomplete: Prefix Navigation plus DFS
Autocomplete is the canonical real-world trie application. Given a prefix, find all stored words that start with it. The approach has two phases: navigate to the prefix node (O(P) where P is the prefix length), then DFS the subtree to collect all words below it. Only branches under the prefix are explored, so words that do not share the prefix are never visited.
Autocomplete
Trie stores: cab, car, card, care, cat, cone. User starts typing a search query.
Autocomplete navigates to the prefix node, then runs DFS below it to collect all completions.
Replace Words: Shortest Prefix Match
Replace Words asks: given a dictionary of root words and a sentence, replace each word in the sentence with its shortest root. For example, with roots ["cat", "bat", "rat"] and sentence "the cattle was rattled by the battery," the result is "the cat was rat by the bat."
The trie approach: insert all roots, then for each word in the sentence, walk the trie. The moment you hit a node with is_end = True, you have found the shortest root. Return that prefix instead of the full word.
Binary Trie for XOR Problems
A binary trie stores integers as paths of bits (0 and 1) from the most significant bit (MSB) to the least significant bit (LSB). This enables greedy bit-by-bit maximum XOR queries. The classic problem: given an array of integers, find the maximum XOR of any two numbers.
To maximize XOR with a number x, at each bit position you want the opposite bit. If x has a 1 at position i, you want a 0 at position i (and vice versa). A binary trie lets you greedily choose the opposite bit at each level.
Why the Runtime Works
Every core trie operation (insert, search, startsWith) takes O(L) time where L is the length of the word or prefix. Each character maps to exactly one edge traversal. There is no hashing of the full string, no comparison against other entries, and no sorting. The cost is proportional to the length of the input string, nothing else.
Word Search II is where the trie saves the most work. Without a trie, searching for k words on an m x n board requires k separate DFS passes, each potentially visiting all cells. With a trie, a single DFS from each cell checks all k words simultaneously. At every cell, the trie either confirms that some target word continues along the current path (and the DFS proceeds) or confirms that no target word can be formed (and the DFS prunes that branch). After finding a word, removing it from the trie means future DFS calls skip paths that can no longer produce results. The total work is bounded by the trie size plus the board exploration, not by k times the board exploration.
Wildcard search has a variable cost. When a character is specific, the search follows one child and the cost is O(L). When a character is ".", the search branches to all children of the current node. The worst case (a pattern of all dots) visits every node in the trie, which is O(N) where N is the total number of nodes. In practice, most patterns have enough specific characters to constrain the search early, and only a few branches survive to deeper levels.
Space depends on prefix overlap. In the worst case (no shared prefixes), n words of length L create O(n * L) nodes, each storing up to ALPHABET_SIZE child pointers. When words share prefixes, the overlapping portion is stored once. For 26 lowercase letters with array-based children, each node uses 26 pointers. For HashMap-based children, each node stores only the children that exist, using less memory when the alphabet is sparse.
When This Pattern Breaks
A trie is not always the right choice. If the problem only needs exact string lookups with no prefix operations, no wildcard matching, and no multi-word simultaneous search, a HashMap is simpler and uses less memory. Both give O(L) lookup for a string of length L, but the HashMap does not allocate a tree of nodes.
Large or unpredictable character sets make tries expensive. Each node needs a mapping from characters to children. With only 26 lowercase letters, a fixed-size array works well. With Unicode or mixed-case input, each node needs a HashMap, and the overhead per node grows. If the problem constraints do not require prefix operations, avoiding the trie entirely is simpler.
Memory can be a concern. A trie for n words of average length L creates up to n * L nodes, each storing child pointers. When words share few prefixes, the trie degenerates into separate chains with no compression benefit. In that case, the trie uses more memory than a flat list of strings.
Frequent deletion adds complexity. Removing a word requires walking to the end, clearing the end marker, then backtracking to prune nodes that no longer serve any word. This is O(L) but involves recursive cleanup logic. If the problem requires many insertions and deletions without prefix queries, a HashSet handles both operations more simply.
Trie vs HashMap vs Sorted Array
Both tries and HashMaps are O(L) for exact lookups. Hashing a string of length L is O(L). The trie wins when you need prefix-based operations.
| Operation | Trie | HashMap / HashSet | Sorted Array |
|---|---|---|---|
| Exact lookup | O(L) | O(L) amortized | O(L log n) |
| Prefix check | O(P) | O(n * L) scan | O(L log n) |
| All words with prefix | O(P + results) | O(n * L) scan | O(L log n + results) |
| Alphabetical order | DFS traversal | Sort needed | Already sorted |
| Space | O(total chars * A) | O(total chars) | O(total chars) |
| Wildcard search (.) | DFS branching | Not supported | Not supported |
Use a trie when:
- •The problem involves finding or checking prefixes of strings
- •You need to search a board or text for multiple patterns simultaneously
- •Autocomplete or suggestion features are required
- •Wildcard matching (".") needs to explore multiple branches
- •You need the shortest prefix matching a word (Replace Words)
Debugging the Trie
When a trie solution produces wrong results, work through these diagnostic questions.
Does search return True for prefixes that were never inserted? The is_end check is missing. Without it, any prefix of an inserted word is reported as found. Both search and startsWith traverse the same path, but search must additionally confirm that the final node marks a complete word.
Does Word Search II produce duplicates or hit TLE? After finding a word, set child.word = None to prevent the same word from being added again. Then prune empty branches with if not child.children: del node.children[char]. Without the prune step, the trie retains paths that can no longer produce new words, causing redundant DFS exploration on large inputs.
Does the board DFS produce wrong paths? Check whether the cell is being restored after backtracking. Marking a cell as visited with board[r][c] = '#' and forgetting to restore it with board[r][c] = char breaks all other DFS paths that need to use that cell.
Does the binary trie produce wrong XOR values? Check the bit range. For 32-bit non-negative integers, iterate from bit 31 down to bit 0 using range(31, -1, -1). Starting from bit 30 or stopping before bit 0 loses precision. Also verify that the opposite-bit logic correctly picks 1 - bit and falls back to the same bit when the opposite does not exist.
Does wildcard search return wrong results? When the character is ".", the search must branch to all existing children. If the code only checks a subset or does not recurse into every child, it will miss valid matches. Also verify the base case: when the index reaches the end of the pattern, return node.is_end, not True.
HashMap vs Array Children
| Aspect | HashMap (dict) | Array [None]*26 |
|---|---|---|
| Flexibility | Any character set | Only lowercase a-z |
| Speed | Hash overhead | Direct index, faster |
| Space | Only stores used chars | Allocates 26 slots per node |
| Iteration | Unordered | Naturally alphabetical |
| Best for | Unicode, mixed case | Lowercase-only problems |
Edge Cases Checklist
- Empty string: should it be a valid word? Usually no, but check the constraints.
- Single character words: ensure your loop handles length-1 strings correctly.
- Duplicate insertions: inserting the same word twice should not break anything (is_end is already True).
- Word is a prefix of another word: "app" and "apple" must both work correctly.
- All same characters: "aaa" and "aaaa" should create a linear chain with two is_end markers.
Practice Problems
Work through these problems in order. The first three build core trie skills. The remaining problems apply tries to increasingly complex scenarios.
Core Trie Problems
| Problem | Difficulty | Approach |
|---|---|---|
| Implement Trie (Prefix Tree) | Medium | The template problem. Insert walks the trie creating nodes for each character, search walks and checks the end flag, startsWith walks and returns true if the path exists. Each node is a hashmap of children. |
| Design Add and Search Words | Medium | Same trie, but search must branch at every "." character using DFS. Each dot tries all 26 children and returns true if any path completes the word. Prune early when a child doesn't exist. |
| Word Search II | Hard | Build a trie from the word list, then DFS from every board cell using the trie to prune dead branches. Remove words from the trie after finding them to skip duplicate work. |
Applied Trie Problems
| Problem | Difficulty | Approach |
|---|---|---|
| Replace Words | Medium | Insert all roots into a trie. For each word in the sentence, walk the trie and return the root as soon as an end flag is hit. If the walk fails before any end flag, keep the original word. |
| Maximum XOR of Two Numbers | Medium | Build a binary trie storing each number bit by bit from the MSB. For each number, greedily pick the opposite bit at every level to maximize XOR. O(32n) time. |
| Design Search Autocomplete System | Hard | Store sentences in a trie with frequency counts at terminal nodes. On each typed character, walk to the prefix node and collect the top 3 results by frequency using a min heap or sort. |
| Search Suggestions System | Medium | Insert all products into a trie. At each character of the search word, collect up to 3 lexicographically smallest products from the current subtree. DFS or precomputed sorted lists both work. |
| Concatenated Words | Hard | Insert all words into the trie. For each word, use DP to check if it splits into two or more existing trie words. Process shorter words first so longer words can reference them. |
| Prefix and Suffix Search | Hard | Encode both prefix and suffix into one key (e.g., suffix + "#" + word) so a single trie lookup handles both constraints at once. Trade space for query speed. |
Reference Templates
Compact code shapes for quick recovery. Each template shows the minimal working pattern.
TrieNode (dict and array variants)
Use dict children for any character set. Use the array variant when the problem constrains input to lowercase letters only.
Insert / Search / StartsWith
The _find helper factors out shared traversal. Search adds an is_end check on top.
Wildcard Search DFS
On a dot, branch to all children. On a letter, follow that child or fail.
Word Search II: Trie-Guided DFS
Store the word at the leaf. Prune empty branches after finding words.
Autocomplete: Prefix Navigation plus DFS
Navigate to the prefix node, then DFS below it to collect all words.
Replace Words: Shortest Prefix
Walk the trie character by character. Return the prefix at the first is_end hit.
Binary Trie: Insert and Max XOR Query
Store numbers as bit paths from MSB to LSB. Query greedily picks the opposite bit.
Deletion and Pruning
Navigate to the word end, clear is_end, then backtrack and remove childless nodes.
Counting Trie Node
Track how many words pass through each node and how many times a word was inserted.
Pattern Recap
Core operations. Insert walks the trie creating nodes for each character and marks the end. Search walks the trie and checks is_end at the final node. StartsWith walks the trie and confirms that the path exists. The only difference between search and startsWith is that one boolean check.
Wildcard search. When the character is specific, follow that one child. When the character is ".", branch to every child and return True if any branch completes the word. Worst case (all dots) visits every node. Patterns with specific characters constrain the search early and prune most branches.
Word Search II. Build a trie from all target words, then run a single DFS from each board cell. The trie prunes branches that cannot lead to any word. After finding a word, remove it from the trie and prune empty branches to prevent TLE. Store the complete word at the leaf to avoid path reconstruction.
Autocomplete. Navigate to the prefix node in O(P) time. DFS below that node to collect all words in the subtree. Sort children at each level for lexicographic order when using HashMap-based children.
Replace Words. Walk the trie one character at a time. The first is_end hit is the shortest root, because the trie is walked from shortest to longest prefix. No need to check all roots individually.
Binary trie. Store integers as bit paths from MSB to LSB. To maximize XOR, greedily pick the opposite bit at each level. Higher bits have exponentially more value, so the greedy choice at each level is safe.
Rebuilding the Pattern
When a trie problem feels unclear, start with one question: does this problem benefit from shared-prefix structure? If the problem involves checking whether strings share a prefix, finding all strings with a given prefix, searching for multiple patterns simultaneously, matching with wildcards, or finding the shortest prefix of a word, the answer is yes. If the problem only needs exact string matching with no prefix operations, a HashMap is simpler and equally fast.
Once the trie is justified, ask what role it plays. In the Implement Trie problem, the trie is the data structure itself, and the task is building it correctly. In Word Search II, the trie is a pruning filter that guides a board DFS. In autocomplete, the trie is a navigation structure that scopes a collection DFS to only the relevant subtree. In Replace Words, the trie is a shortest-match finder where walking the tree from root to the first end marker gives the answer directly.
Then ask what each node needs. Most problems need only children and is_end. Word Search II benefits from storing the full word at the leaf to avoid path reconstruction during DFS. Counting problems need prefix_count or word_count. Binary tries replace character children with two-element arrays indexed by bit value.
The pattern is recoverable from three decisions: whether shared-prefix structure helps, what role the trie plays in the algorithm, and what each trie node must store. From those three answers, the code shape follows directly.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Take Assessment
Test Your Understanding
12 questions covering trie operations, wildcard search, Word Search II, and binary tries.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Tries in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.