Overview
A trie stores a set of strings character by character. The root represents the empty string, each edge adds one character, and a flag marks nodes where a complete word ends. Because words with a common prefix share the same path, checking whether any word starts with "algo" costs four steps no matter how many words are stored.
Tries shine when you have many queries against one dictionary: autocomplete suggestions, spell checking, replacing words by their roots, or searching a grid for many words at once (build one trie, run one DFS). A binary version — a trie over the bits of numbers — finds the maximum XOR pair in linear time.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Insert / search / startsWith | O(L) per word |
| Build from words | O(total characters) |
| Space | O(total characters × alphabet) worst case with arrays |
Patterns to recognise
Prefix lookup
Use it for: Autocomplete, search suggestions, replace words.
Walk to the prefix node, then collect or check below it.
Many words, one search
Use it for: Word Search II, concatenated words.
Build one trie from all words and traverse it alongside the search.
Bitwise greedy
Use it for: Maximum XOR of two numbers.
For each bit, prefer the child that differs from the current number.
Code template
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node['#end'] = True
def _walk(self, text):
node = self.root
for ch in text:
if ch not in node:
return None
node = node[ch]
return node
def search(self, word):
node = self._walk(word)
return node is not None and '#end' in node
def starts_with(self, prefix):
return self._walk(prefix) is not None
class Trie {
struct Node {
array<unique_ptr<Node>, 26> next;
bool end = false;
};
Node root;
const Node* walk(const string& s) const {
const Node* node = &root;
for (char c : s) {
node = node->next[c - 'a'].get();
if (!node) return nullptr;
}
return node;
}
public:
void insert(const string& word) {
Node* node = &root;
for (char c : word) {
auto& child = node->next[c - 'a'];
if (!child) child = make_unique<Node>();
node = child.get();
}
node->end = true;
}
bool search(const string& word) const {
const Node* node = walk(word);
return node && node->end;
}
bool startsWith(const string& prefix) const { return walk(prefix) != nullptr; }
};
Common mistakes
- Forgetting the end-of-word flag makes every prefix look like a word.
- A 26-slot array per node is fast but memory hungry; use a hash map for large alphabets.
- In Word Search II, remove found words (or prune empty branches) to avoid duplicates and timeouts.
Quick check
Three questions on Tries. Get all three right to earn +15 XP.
-
Looking up a word of length L in a trie costs:
You follow one child pointer per character, regardless of how many words are stored.
-
What does the end-of-word flag on a trie node tell you?
Without it you could not tell the word "app" from a mere prefix of "apple".
-
Which task is a trie especially good at?
Walk down the prefix once, then every word below that node matches.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Implement Trie (Prefix Tree)LeetCode Medium +40
- Design Add and Search Words Data StructureLeetCode Medium +40
- Replace WordsLeetCode Medium +40
- Longest Word in DictionaryLeetCode Medium +40
- Search Suggestions SystemLeetCode Medium +40
- Maximum XOR of Two Numbers in an ArrayLeetCode Medium +40
- Word Search IILeetCode Hard +70
Stuck on Tries?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor