Insert words, search prefixes and explore autocomplete with an interactive trie visualizer. Follow each character through the prefix tree.
Seeded with "cat", "car", "card", "care", "dog", "do". Nodes with a double ring end a word; every other node is only a prefix.
Press Start.
How it works: Trie (Prefix Tree)
Step by step
- Current node and the path to it
- Node just created
- A word ends here (double ring)
- Words matched by a prefix query
- Lookup fell off the trie
Press Start or Step: the step the animation is on lights up below.
- 1
Start at the root
The root stands for the empty prefix. Every insert, search and prefix query begins there.
node = root - 2
Letter exists → follow it
There's already a child for the next letter, so move down to it. When inserting, this is prefix sharing: no new node needed.
node = node.children[ch] - 3
Letter missing (insert) → add a node
No word stored so far continues with this letter, so make a new child and keep going.
node.children[ch] = TrieNode() - 4
Mark where the word ends
After the last letter, flag the node as the end of a word. Without the flag, “car” would be indistinguishable from the prefix of “card”.
node.is_end = True - 5
Letter missing (lookup) → not found
The path falls off the trie, so no stored word starts this way. Stop early: there's no need to look at anything else.
if ch not in node.children: return False - 6
All letters matched → check the end flag
The word is stored only if its last node is flagged. If every letter matched but the flag is off, it's just a prefix of longer words.
return node.is_end - 7
Collect every word below the prefix
Everything under the prefix's node starts with that prefix. A depth-first walk of that subtree gathers each flagged node.
dfs(node): if node.is_end: yield word - 8
Done
The trie now holds every inserted word, with shared prefixes stored once.
A trie stores strings one character per level. Each node stands for a prefix, and its children are the letters that can follow it. Words that start the same way share the same path, so “car”, “card ” and “care” share the nodes c → a → r.
Every operation is a walk from the root, one letter at a time. Insert creates any missing nodes. Search and prefix queries just follow the existing ones. The cost depends on the length of the word, not on how many words are stored.
Reaching a node is not the same as finding a word. “ca” has a node because “cat” passes through it, but nobody inserted “ca”. A flag on the node where each inserted word ends (the double ring here) is the only thing that tells a stored word from a prefix.
Spot it in an interview
- “Implement autocomplete”, “search suggestions”, “startsWith”, or “longest common prefix”.
- Word search on a grid with many target words: walk the grid and the trie together and prune any path that isn't a prefix.
- Any time you need many prefix lookups. A hash set can say whether a whole word exists, but not which words begin with a prefix.
Insert and search touch one node per letter of the word, however many words are stored. A prefix query costs O(L) to reach the prefix, plus the size of the subtree it collects. In the worst case, with no shared prefixes, the trie stores one node per letter of every word.