Explore trie interview patterns with interactive prefix trees, wildcard search and Word Search II. Follow each letter and study Python solutions.
The pattern
Tries: store words letter by letter, share the prefixes
A trie (prefix tree) stores words as paths from an empty root, one letter per node. Words with the same prefix share the nodes for it, so checking a word or a prefix takes one step per letter, however many words are stored. And one walk down the trie checks every word that shares the path at once.
1Shared prefixes share a path
car, cat, cart and do. Each node is one letter, a path from the root spells a prefix, and a double ring marks where a word ends. cart reuses the whole car path.
2A wildcard tries every child
Searching .ad: the dot could be any letter, so try each child of the root in turn and keep going from there. The first branch that reaches a word end answers true.
3Many words, one search
For Word Search II, walk the board and the trie together. A step is only taken if the next letter is a child in the trie, so cat, car and cart are all checked by the same walk.
How to spot it
- Prefix questions: “does any word start with …”, autocomplete, the longest common prefix.
- Wildcards in a dictionary lookup: branch over the children at each wildcard.
- Many words searched in one place (a board, a stream of letters): one trie, one search, instead of one search per word.
Reading the pictures
- The top circle is the empty root. Each node below it is one letter; children are in alphabetical order.
- A double ring means a word ends at that node. Without it, the path is only a prefix of longer words.
- To insert and search your own words, try the Trie visualizer.
NeetCode 150 · Tries
All 3 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Implement Trie (Prefix Tree)
MediumBlind 75Build a trie with insert(word), search(word) (is this exact word stored?) and startsWith(prefix) (does any stored word start with it?).
insert apple, search apple, search app, startsWith app, insert app, search app
calls
the trie (double ring = a word ends here)
variables
- results (search / startsWith)
- –
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(L) per call
- 24 ops
- Brute force
- 28 ops
On a bigger input (150 words, then 150 searches):
- Pattern
- 1,837 ops
- Brute force
- 32,462 ops
Keep the words in a plain list: every search or startsWith compares the query with every stored word, O(n · L) per query instead of O(L).
“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.
How it works: Implement Trie (Prefix Tree)
Step by step
- Current node
- Path walked so far
- Node just created
- No child for the next letter
Press Start or Step: the step the animation is on lights up below.
- 1
An empty root
self.root = TrieNode() # children = {}, end = False - 2
Follow the child for the next letter
cur = cur.children[c] - 3
insert: missing child → create it
if c not in cur.children: cur.children[c] = TrieNode() - 4
insert: mark the last node
cur.end = True - 5
search / startsWith: answer
search needs the end mark; startsWith doesn't.
return cur.end # or True for startsWith - 6
All calls answered
Each node is a map from a letter to a child node, plus a flag for “a word ends here”. The root is empty. A path from the root spells a prefix.
insert walks the word letter by letter, creating children that don't exist, and marks the last node. search walks the same way and needs every letter and the end mark. startsWith only needs every letter. All three are O(length of the word), however many words are stored.
Spot it in an interview
- Many words and questions about prefixes: autocomplete, spell checking, “does any word start with …”.
- Searching many words at once (Word Search II): one walk down the trie checks them all.
Each call visits one node per letter of its word; nodes are shared by words with the same prefix.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.