Notes › DSA
Trie (Prefix Tree)
A trie stores strings one character per level. Words that share a prefix share the same path, so prefix questions are very fast.
insert: "cat", "car", "dog"
(root)
/ \
c d
| |
a o
/ \ |
t* r* g* * = end of a word
Node and operations
struct TrieNode {
TrieNode* child[26] = {}; // for lowercase a–z
bool isEnd = false;
int prefixCount = 0; // how many words pass through here (optional)
};
class Trie {
TrieNode* root = new TrieNode();
public:
void insert(const string& w) {
TrieNode* cur = root;
for (char c : w) {
int i = c - 'a';
if (!cur->child[i]) cur->child[i] = new TrieNode();
cur = cur->child[i];
cur->prefixCount++;
}
cur->isEnd = true;
}
bool search(const string& w) { // whole word
TrieNode* n = walk(w);
return n && n->isEnd;
}
bool startsWith(const string& p) { // any word with this prefix
return walk(p) != nullptr;
}
int countPrefix(const string& p) {
TrieNode* n = walk(p);
return n ? n->prefixCount : 0;
}
private:
TrieNode* walk(const string& s) {
TrieNode* cur = root;
for (char c : s) {
cur = cur->child[c - 'a'];
if (!cur) return nullptr;
}
return cur;
}
};
Complexity
| Operation | Time |
|---|---|
| Insert / search / startsWith | O(L) — L = length of the word, independent of how many words are stored |
| Space | O(total characters × alphabet size) in the worst case |
For a big or unknown alphabet, use unordered_map<char, TrieNode*> instead of a fixed array (less memory, a bit slower).
Trie vs hash set
| Hash set | Trie | |
|---|---|---|
| Exact lookup | O(L) average | O(L) |
| Prefix search ("words starting with ca") | O(n · L) — check every word | O(L) |
| Sorted output | no | yes (DFS in letter order) |
| Memory | lower | higher |
Uses
- Autocomplete / search suggestions — walk to the prefix, then DFS to list words.
- Spell checkers, dictionary word games (Boggle).
- Word search II — put all words in a trie and DFS the grid once.
- Longest common prefix of many strings.
- Maximum XOR of two numbers — a binary trie of 32 bits; for each number, greedily walk towards the opposite bit.
- IP routing (longest prefix match).
Deleting a word
Clear isEnd; optionally remove nodes on the way back up if they have no children and are not the end of another word (decrement prefixCount).
Classic problems
| Problem | Idea |
|---|---|
| Implement Trie | insert / search / startsWith |
Design add and search words (with . wildcard) |
DFS on . |
| Word search II | trie + grid DFS |
| Longest word in dictionary | words whose every prefix is a word |
| Replace words | shortest root prefix |
| Maximum XOR of two numbers | binary trie |
| Search suggestions system | trie + DFS (or sorting + binary search) |
Practise in the Trie section.
Interview one-liners
- A trie answers prefix queries in O(prefix length).
- The root is empty;
isEndmarks where a word stops (so "car" and "cart" can both exist). - Memory is the cost — 26 pointers per node.