Tries
A trie stores strings one character per edge, so words that share a prefix share the same path through the tree.
Loading visual…
Definition
A trie, short for retrieval tree and usually pronounced like 'try', stores a set of strings by turning each one into a path from the root, one character per edge. The root represents the empty string, and following an edge labeled with a character moves to the node representing the string built so far plus that character. Because the path is shared, any two words that start with the same letters share that same prefix path through the tree and only branch apart at the first character where they differ; each node also needs some marker, often a boolean flag, saying whether the string ending at that node is actually a complete word that was inserted, rather than just a prefix of a longer one. Both inserting and searching a trie cost O(L), where L is the length of the string being processed, and that cost does not grow with however many other words are already stored, unlike scanning a list of strings one at a time. This is what makes tries well suited to prefix-based queries: checking whether any stored word starts with a given prefix, or listing every word that does, only means walking down to the node for that prefix and, for listing, exploring everything below it. The trade-off is memory: a trie can use noticeably more space than a plain hash set of the same strings, because every distinct prefix, not just every complete word, gets its own node.
Examples
class TrieNode {
children = {};
isWord = false;
}
class Trie {
root = new TrieNode();
insert(word) {
let node = this.root;
for (const ch of word) {
node.children[ch] ??= new TrieNode();
node = node.children[ch];
}
node.isWord = true;
}
}
const trie = new Trie();
trie.insert("cat");
trie.insert("car");Inserting car walks the same c and a nodes that cat already created, only branching off into a new node at r, so the shared prefix ca is stored once.
search(word) {
let node = this.root;
for (const ch of word) {
if (!node.children[ch]) return false;
node = node.children[ch];
}
return node.isWord;
}The walk fails early the moment a needed character edge is missing, and even reaching the end successfully only counts as a match if isWord is actually set on that final node.
startsWith(prefix) {
let node = this.root;
for (const ch of prefix) {
if (!node.children[ch]) return false;
node = node.children[ch];
}
return true;
}
trie.startsWith("ca"); // true
trie.startsWith("cot"); // falseUnlike search, startsWith does not check isWord at the end, since a prefix only needs to exist along some path, not be a complete word itself.
Common mistakes
- Forgetting to mark isWord (or equivalent) at the end of insert, which makes every inserted string look like just a prefix, never a complete match.
- Confusing search (must land on a complete word) with startsWith (only needs the path to exist), and using one where the other is needed.
- Assuming a trie always saves memory; many short, unrelated strings with little shared prefix can use more space than a plain hash set.
Key takeaways
- Each edge in a trie is one character, and words that share a prefix share that same path from the root.
- Insert and search both cost O(L), the length of the string, regardless of how many other words are stored.
- A node needs an explicit end-of-word marker, since reaching a node by walking a prefix does not by itself mean a full word ends there.
The words 'cat' and 'car' are both inserted into an empty trie. What do their paths from the root look like?
Where you see this
- Autocomplete and search-as-you-type suggestions in a search bar.
- Spell checkers, finding whether a word or a close variant is in a dictionary.
- IP routing tables, matching the longest known prefix of an address.
- Storing a dictionary compactly when many words share long prefixes.