Trie
A Trie (pronounced "try") is a special tree data structure used mainly for storing and searching strings/prefixes.
It is also called a:
Prefix Tree
The main idea is:
Each path from the root represents characters of a word.
Tries are especially useful for prefix-based searching.
1. Why Do We Need a Trie?
Suppose we have these words:
apple app application apply banana ball bat
If we want to find all words beginning with:
app
a Trie is very useful.
It organizes the common prefix:
root | a | p | p / | \ l ? ...
The words:
app apple application apply
share:
app
A Trie stores this common part only once.
2. Basic Trie Structure
Suppose we insert:
cat car can
The Trie looks conceptually like:
root | c | a / | \ t r n
Notice that cat, car, and can share:
ca
So we don't store c and a separately for every word.
3. Trie vs Binary Tree
A normal binary tree has at most:
2 children
A Trie can have many children.
For lowercase English letters:
a b c d e f ... z
A node can have up to:
26 children
Example:
root / | \ a b c / \ p a
4. Important Trie Concepts
There are three important concepts:
Root
The starting node.
root
It does not represent a character.
Child
A character connected to another character.
End of Word
We need to know whether a path represents a complete word.
For example:
app apple
The path app exists in both words.
But:
app
must be marked as a complete word.
So we use:
isEndOfWord
5. Why isEndOfWord Is Important
Consider:
app apple
Trie:
root | a | p | p | l | e
How do we know whether app is a complete word?
We mark the second p:
root | a | p | p* ← complete word | l | e* ← complete word
So:
app → true apple → true
Without isEndOfWord, we wouldn't know whether app was actually inserted or was simply a prefix.
6. Trie Node in C++
For lowercase English letters:
struct TrieNode { TrieNode* children[26]; bool isEndOfWord; TrieNode() { isEndOfWord = false; for (int i = 0; i < 26; i++) { children[i] = nullptr; } } };
Each node has:
26 possible children + end-of-word information
7. Character to Array Index
Suppose:
a b c d ... z
We can convert characters to indexes using:
ch - 'a'
For example:
'a' - 'a' = 0 'b' - 'a' = 1 'c' - 'a' = 2
Therefore:
children[ch - 'a']
lets us access the appropriate child.
8. Inserting a Word
Suppose we insert:
cat
Start at root.
Character c
root | c
Character a
root | c | a
Character t
root | c | a | t*
Then:
isEndOfWord = true;
9. Insert Function
void insert(string word) { TrieNode* current = root; for (char ch : word) { int index = ch - 'a'; if (current->children[index] == nullptr) { current->children[index] = new TrieNode(); } current = current->children[index]; } current->isEndOfWord = true; }
10. Searching a Word
Suppose we inserted:
cat car can
Search:
cat
We follow:
root ↓ c ↓ a ↓ t
If we reach t and:
isEndOfWord == true
then:
cat exists
11. Search Function
bool search(string word) { TrieNode* current = root; for (char ch : word) { int index = ch - 'a'; if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return current->isEndOfWord; }
12. Search vs Prefix Search
This is where Trie becomes powerful.
There are two different questions:
Question 1
Does the word
appexist?
We need:
app exists as a complete word
Question 2
Does any word start with
app?
We only need to know whether the path:
a → p → p
exists.
We don't care whether app itself is a complete word.
13. Prefix Search
Suppose the Trie contains:
apple application apply banana
Search prefix:
app
The path exists:
root | a | p | p
Therefore:
"app" is a valid prefix
C++ startsWith()
bool startsWith(string prefix) { TrieNode* current = root; for (char ch : prefix) { int index = ch - 'a'; if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return true; }
14. Complete Trie Implementation
Here's a basic lowercase-English Trie:
#include <iostream> #include <string> using namespace std; struct TrieNode { TrieNode* children[26]; bool isEndOfWord; TrieNode() { isEndOfWord = false; for (int i = 0; i < 26; i++) { children[i] = nullptr; } } }; class Trie { private: TrieNode* root; public: Trie() { root = new TrieNode(); } void insert(string word) { TrieNode* current = root; for (char ch : word) { int index = ch - 'a'; if (current->children[index] == nullptr) { current->children[index] = new TrieNode(); } current = current->children[index]; } current->isEndOfWord = true; } bool search(string word) { TrieNode* current = root; for (char ch : word) { int index = ch - 'a'; if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return current->isEndOfWord; } bool startsWith(string prefix) { TrieNode* current = root; for (char ch : prefix) { int index = ch - 'a'; if (current->children[index] == nullptr) { return false; } current = current->children[index]; } return true; } }; int main() { Trie trie; trie.insert("apple"); trie.insert("app"); trie.insert("application"); trie.insert("apply"); cout << trie.search("app") << endl; cout << trie.search("apple") << endl; cout << trie.search("banana") << endl; cout << trie.startsWith("app") << endl; cout << trie.startsWith("ban") << endl; return 0; }
Output:
1 1 0 1 0
Where:
1 = true 0 = false
15. Trie Complexity
Let:
L = length of the word
Then:
Insert
O(L)
Search
O(L)
Prefix Search
O(L)
This is one of the biggest advantages of Trie.
It depends mainly on the length of the word, not directly on the number of words stored.
16. Example
Suppose we have:
10,000,000 words
and want to search:
computer
The word has:
8 characters
Trie search follows approximately:
c → o → m → p → u → t → e → r
So the operation depends on:
L = 8
rather than checking millions of complete words one by one.
17. Trie vs Hash Table
Both can be useful for strings.
Hash Table
unordered_set<string>
Excellent for:
"Does this exact word exist?"
Average:
O(1)
Trie
Excellent for:
"Does this prefix exist?" "What words start with 'app'?"
Complexity:
O(L)
So:
Hash Table → Exact lookup Trie → Prefix lookup
18. Autocomplete
One of the most common real-world applications.
Suppose you type:
app
Google/search engine can suggest:
apple application apply app store
A Trie can store:
apple application apply appstore
and use the prefix:
app
to find all matching words.
Conceptually:
root | a | p | p / | \ l l s | | | e y t...
This is why Tries are often called Prefix Trees.
19. Spell Checker
Suppose a dictionary contains:
cat car can computer coding
A spell checker can use a Trie to efficiently determine whether a word exists.
For:
comp
the Trie can also tell us that it is a valid prefix.
20. Word Search
Tries are useful in problems involving:
dictionary prefixes multiple words word search
For example:
Given: apple app ape bat ball Find all words beginning with: ap
Answer:
apple app ape
21. Trie for Lowercase Letters
Our implementation uses:
TrieNode* children[26];
So it supports:
a-z
If we need uppercase letters too, we could use:
52 children
Or use a map:
unordered_map<char, TrieNode*> children;
This can save memory when a node has only a few actual children.
22. Array vs Map Implementation
Array
TrieNode* children[26];
Advantages:
- Fast
- Simple
- O(1) character access
Disadvantage:
- Can consume more memory
unordered_map
unordered_map<char, TrieNode*> children;
Advantages:
- Stores only characters that actually exist
- Useful for larger character sets
Disadvantage:
- More overhead
- Hashing involved
23. Trie Deletion
Deletion is more complicated than insertion/search.
Suppose:
app apple
Trie:
a → p → p* → l → e*
If we delete:
apple
we should not delete the app path because:
app
is still a valid word.
So deletion must determine whether nodes are still needed.
24. Trie Deletion Idea
There are two things to consider:
Case 1
The word is a prefix of another word.
app apple
Deleting app:
app* → apple
We only change:
isEndOfWord = false
The nodes remain.
Case 2
The word has no other word using its path.
Then unnecessary nodes can be deleted.
25. Trie vs BST vs Heap
Now you have learned three important tree-based structures.
| Structure | Main Purpose |
|---|---|
| Binary Tree | Hierarchical data |
| BST | Ordered searching |
| Heap | Priority / min-max |
| Trie | Strings / prefixes |
Think:
BST ↓ "Find this value efficiently" Heap ↓ "Give me highest/lowest priority" Trie ↓ "Find words/prefixes"
26. Trie vs Binary Search Tree
Suppose we store:
apple application apply
A BST compares complete strings:
"apple" < "application"?
A Trie instead follows characters:
a ↓ p ↓ p ↓ l ↓ ...
Therefore, Trie naturally represents shared prefixes.
27. Important Trie Problems
After learning the basics, common DSA problems include:
- Implement Trie
- Search a word
- Prefix search
- Insert words
- Delete a word
- Autocomplete
- Word dictionary
- Longest common prefix
- Word Search II
- Count words with a given prefix
- Count distinct substrings
- Maximum XOR using Binary Trie
The last one is particularly interesting:
Binary Trie
Instead of storing letters:
a-z
we store:
0 and 1
This is useful for XOR-related problems.
28. Important Mental Model
Think about a Trie like a road map of characters.
For:
cat car can
all three journeys start:
c → a
Then they split:
c | a / | \ t r n
So:
Common prefixes share the same path.
That's the core idea of a Trie.
🧠 Final Summary
Remember these points:
1. Trie = Prefix Tree. 2. Mainly used for strings. 3. Each edge/node represents a character. 4. Common prefixes share nodes. 5. isEndOfWord tells us whether a complete word ends there. 6. Insert → O(L) 7. Search → O(L) 8. Prefix → O(L) 9. Excellent for autocomplete and prefix searching. 10. Trie is different from BST: BST → ordered values Trie → characters/prefixes
Where:
L = length of the word/prefix
Your roadmap now reaches:
Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie ↓ Graphs ↓ Graph Traversal