Trie (prefix tree)
mediumNo node stores a word - a word exists when a path of edges spells it and ends on a node flagged as a word end. Shared prefixes cost nothing extra, which is what makes autocomplete cheap.
O(length of the key)Space O(total characters × alphabet)Saved in this browser - no sign-up, nothing sent anywhere.
How trie (prefix tree) works
A trie stores no word in any node. A word exists when a path of edges spells it out, character by character from the root, ending at a node whose end flag is set. Insert "car" and then "card" and they share the whole c-a-r path - the longer word costs one extra node. Shared prefixes are stored exactly once, and that sharing is the entire economy of the structure.
Every operation is the same walk. Insert follows the word's characters, creating a child node only where an edge is missing, then flags the final node. Search walks the path and reports whether the last node is flagged; startsWith walks and only asks whether the path survived. All three cost O(length of the key) - the same whether the trie holds ten words or ten million.
The trade is memory: every node carries a child table, so long keys with little sharing can cost far more than a hash set holding the same words. Compressed variants - radix trees, Patricia tries - collapse single-child chains into one labelled edge to win that space back. Reach for a trie the moment prefixes matter; a hash map can only ever answer exact keys.
Step by step
- Insert "cat" into an empty trie: the root grows a c child, c grows a, a grows t, and the t node is flagged as a word end.
- Insert "car": c and a already exist, so the walk reuses them and only creates r. One new node instead of three.
- Insert "card": walk c-a-r free of charge, add d, flag it. The r node keeps its flag - it is both a word and a prefix.
- Search "car": follow c, then a, then r. The path exists and the final node is flagged - found.
- Search "ca": the path exists, but the a node carries no flag - "ca" is only a prefix, not a stored word.
- startsWith("ca") asks less: the path survived, so completions exist. Every flagged node below - cat, car, card - is a suggestion.
- Search "cow": from c there is no o edge, so the walk dies at the second character without touching any stored word.
Complexity
| Worst case time | O(length of the key) |
|---|---|
| Space | O(total characters × alphabet) |
Independent of how many words are stored - only key length matters.
Reference implementation
Python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True # without this, "car" would
# match just because "card" exists
def search(self, word):
node = self._walk(word)
return node is not None and node.is_end
def starts_with(self, prefix):
return self._walk(prefix) is not None
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node.children:
return None
node = node.children[ch]
return nodeJavaScript
class Trie {
#root = { children: new Map(), isEnd: false };
insert(word) {
let node = this.#root;
for (const ch of word) {
if (!node.children.has(ch))
node.children.set(ch, { children: new Map(), isEnd: false });
node = node.children.get(ch);
}
node.isEnd = true;
}
#walk(s) {
let node = this.#root;
for (const ch of s) {
node = node.children.get(ch);
if (!node) return null;
}
return node;
}
search(word) { return this.#walk(word)?.isEnd ?? false; }
startsWith(prefix) { return this.#walk(prefix) !== null; }
}Worth noticing
The path is the key
No node stores a whole word. A word exists precisely when there is a path of edges spelling it, ending on a node marked as a word end. Shared prefixes are shared paths - insert 'car' and 'card' and only one new node appears.
Lookup is O(length), independent of how many words are stored
A hash map of a million words still hashes the whole key; a trie walks one character at a time and stops the instant the path dies. For prefix queries - autocomplete - a hash map cannot help at all.
The isEnd flag is not optional
Without it, searching for 'car' would succeed merely because 'card' was inserted. The flag is what distinguishes 'this path exists' from 'this path is a word'.
Memory is the trade
Each node carries a child map. For sparse, long keys a trie can use far more memory than a hash set - which is why compressed variants (radix trees, Patricia tries) collapse single-child chains into one edge.
Common pitfalls
- Skipping the end-of-word flag. Without it, searching "car" succeeds merely because "card" was inserted - path existence and word existence are different questions.
- Deleting by removing path nodes outright. "car" shares nodes with "card"; correct deletion unflags the final node and prunes only chains no other word still uses.
- Allocating a fixed 26-slot child array per node on sparse data - memory multiplies fast. Use a map per node, or a radix tree, when the alphabet is wide or usage thin.
- Not normalising input. Insert "Car" and search "car" and they take different paths - case, accents, and charset must be canonical before any walk.
Where it is used
- Autocomplete and search-as-you-type: walk the prefix once, then every flagged node below it is a suggestion.
- Spell checkers and dictionary lookups, where a dead path exits early instead of hashing every candidate.
- IP routing tables: longest-prefix match over bit strings is a trie walk - Patricia tries in practice.
- Interview problems: Word Search II, add-and-search with wildcards, replace words - all built on the same walk.
Frequently asked questions
What is the time and space complexity of a trie?
Insert, search, and startsWith are all O(length of the key) - the walk touches one node per character, independent of how many words are stored. Space is O(total characters × alphabet): each stored character owns a node, and every node carries child capacity proportional to the alphabet size.
When should I use a trie instead of a hash map?
When prefixes matter. A hash map answers exact-key lookups but hashes the entire key every time and cannot enumerate keys by prefix at all. A trie walks character by character, exits early on dead paths, and hands you every completion of a prefix - which is exactly what autocomplete needs.
Why does a trie need an end-of-word flag?
Because a path can exist without being a word. After inserting "card", the walk for "car" succeeds - c, a, r all exist - but nothing records that "car" itself was ever stored. The flag on the final node is the difference between "this path exists" and "this word was inserted".
What is a compressed trie or radix tree?
A trie in which chains of single-child nodes collapse into one edge labelled with the whole substring. Lookups still walk the key once, but node count - and pointer chasing - drops sharply on sparse data. Patricia tries apply the same idea to bit strings; IP routing tables use exactly that form.