Why should you care?
Imagine typing app into a search box and immediately getting:
- apple
- application
- apply
- appointment
How does the system find all words beginning with app so efficiently?
One data structure designed specifically for this kind of problem is a Trie.
Tries are useful for:
- Autocomplete
- Spell checkers
- Search suggestions
- Dictionary implementations
- Prefix matching
- IP routing
- Word games
- Text processing
Unlike many data structures we've studied so far, a Trie is designed around characters and prefixes.
The Problem
Suppose we have these words:
apple
app
application
apply
banana
band
bandage
We want to answer questions such as:
Does "apple" exist?
Does "app" exist?
What words start with "app"?
What words start with "ban"?
A simple approach is to store the words in an array or list and compare each word.
For example:
apple
application
apply
banana
band
bandage
To find words beginning with app, we may have to inspect many strings.
Hash tables are excellent for checking whether an exact word exists:
"apple" → exists
"app" → exists
But they are not naturally designed for:
"Give me every word beginning with app"
We need a structure that represents shared prefixes efficiently.
That is where a Trie comes in.
The Concept
A Trie is a tree-like data structure used to store strings.
Each path from the root represents characters in a word.
For example, consider:
app
apple
apply
The Trie can look conceptually like:
root
|
a
|
p
|
p
/ | \
l ... y
|
e
The important idea is that common prefixes are shared.
The words:
app
apple
application
apply
all begin with:
app
Instead of storing app repeatedly, the Trie stores those characters along one shared path.
Each node generally contains:
- Links to child nodes
- Information about whether a complete word ends there
For example:
Node
├── children
└── isEndOfWord
Simple Explanation
Think of a Trie as a character-by-character dictionary.
Suppose we insert:
cat
car
can
The Trie begins with:
root
|
c
|
a
Then the paths split:
c
|
a
/ | \
t r n
The prefix:
ca
is shared.
But the final characters:
t
r
n
represent different words.
The key point is:
Each level of the Trie represents another character in the word.
So if we search for:
car
we follow:
root → c → a → r
If the r node marks the end of a word, car exists.
Real-world Analogy
Imagine a large dictionary organized like a filing system.
Instead of sorting complete words alphabetically, you organize them character by character.
Start with:
A
B
C
...
Under C:
CA
CB
CC
CD
...
Under CA:
CAB
CAC
CAD
...
Now suppose you want every word beginning with:
CAR
You simply navigate:
C → A → R
Once you reach CAR, everything below that point represents words beginning with CAR.
That is exactly what a Trie does.
Code Example
Let's implement a simple Trie in Java.
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord;
}
Each node contains 26 possible children:
a → index 0
b → index 1
c → index 2
...
z → index 25
Now let's create the Trie:
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
return current.isEndOfWord;
}
}
We can use it like this:
public class Main {
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("apply");
System.out.println(trie.search("app"));
System.out.println(trie.search("apple"));
System.out.println(trie.search("banana"));
}
}
Output:
true
true
false
How insertion works
When inserting:
apple
we follow:
root
↓
a
↓
p
↓
p
↓
l
↓
e
At e, we set:
isEndOfWord = true;
Now insert:
app
The nodes:
a → p → p
already exist.
We simply follow them and mark the p node as another word ending.
This is why prefixes are shared.
Prefix Search
One of the biggest advantages of a Trie is prefix searching.
Suppose we inserted:
apple
app
application
apply
banana
band
We can ask:
Does any word start with "app"?
We don't need to compare against every word.
We simply follow:
a → p → p
If that path exists, the prefix exists.
A simple prefix-check method:
public boolean startsWith(String prefix) {
TrieNode current = root;
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
return false;
}
current = current.children[index];
}
return true;
}
Now:
trie.startsWith("app");
returns:
true
while:
trie.startsWith("xyz");
returns:
false
Time Complexity
Let:
L = length of the word
Then:
| Operation | Time Complexity |
|---|---|
| Insert | O(L) |
| Search | O(L) |
| Prefix Search | O(L) |
| Delete | O(L) |
The important observation is that the complexity depends on the length of the string, not directly on the number of words stored.
For example, searching for:
application
requires following roughly 11 characters regardless of whether the Trie contains:
100 words
or:
1,000,000 words
The actual performance also depends on the implementation and alphabet.
Common Mistakes
Mistake 1: Thinking every node represents a complete word
Consider:
car
cart
The node representing:
car
is shared by both words.
Therefore, we need:
isEndOfWord
to distinguish between:
car
and:
cart
A node can be:
- A prefix only
- The end of a word
- Both a prefix and the end of a word
Mistake 2: Assuming Tries are always memory efficient
Tries can consume significant memory.
If every node contains:
TrieNode[] children = new TrieNode[26];
each node reserves space for 26 references.
For a large vocabulary, this can become expensive.
Alternative implementations can use:
Map<Character, TrieNode>
instead of a fixed array.
This saves space when each node has only a few children, although hash-map overhead can also be significant.
Mistake 3: Ignoring case and character sets
The example implementation assumes:
a-z
Only.
Real applications may need:
A-Z
0-9
Unicode
spaces
punctuation
A production Trie therefore needs a carefully designed character representation.
Advanced Notes
1. Trie vs Hash Table
A hash table is excellent for:
Does this exact word exist?
A Trie is excellent for:
Does this prefix exist?
What words begin with this prefix?
For example:
Hash Table
apple → value
apply → value
banana → value
Trie:
a
|
p
|
p
├── l → e
└── l → y
The Trie explicitly represents the relationship between strings and their prefixes.
2. Trie vs Binary Search Tree
A Binary Search Tree organizes elements based on comparisons.
A Trie organizes strings based on their characters.
For example:
BST:
Compare complete strings
Trie:
Compare character by character
This makes Tries particularly useful for prefix-based operations.
3. Autocomplete
Suppose a user types:
pro
The application navigates to the node representing:
p → r → o
Then it explores the subtree below that node.
It might find:
program
programming
programmer
project
process
These become autocomplete suggestions.
4. Compressed Trie
A normal Trie can contain many nodes with only one child.
For example:
c
|
o
|
m
|
p
|
u
|
t
|
e
|
r
A compressed Trie can combine chains of single-child nodes:
computer
This reduces the number of nodes and can improve memory usage.
A compressed Trie is also commonly called a Radix Tree or Patricia Trie, depending on the specific variant.
5. Deletion
Deleting a word from a Trie requires care.
Suppose we have:
car
cart
If we delete:
car
we cannot necessarily delete the r node because:
cart
still needs it.
Instead, we can simply change:
isEndOfWord = false;
If the nodes are no longer needed by any other word, they can potentially be removed.
6. Unicode and Memory Optimization
For large-scale systems, a fixed array like:
new TrieNode[26]
may not be appropriate.
Other approaches include:
HashMap
Sorted Map
Compressed Trie
Ternary Search Tree
Memory-mapped structures
The correct choice depends on the alphabet, dataset size, access patterns, and memory constraints.
The Bigger Picture
Look at how our data structures have evolved:
Arrays
↓
Linked Lists
↓
Stacks / Queues
↓
Hash Tables
↓
Trees
↓
Heaps
↓
Graphs
↓
Tries
Each structure solves a different kind of problem.
A Hash Table gives us fast exact lookup.
A Heap gives us efficient priority-based access.
A Graph represents relationships.
A Trie represents strings and their prefixes.
The interesting part is that a Trie is actually built on a familiar idea:
Trie = Tree + Character-based navigation
This is an important connection.
We learned that trees allow one node to have multiple children.
A Trie takes that idea and uses each level to represent another character.
The Most Important Mental Model
Remember this:
A Trie is a tree where each path represents a string, and shared paths represent shared prefixes.
For example:
root
|
c
|
a
/ | \
t r n
The path:
root → c → a → t
represents:
cat
The path:
root → c → a → r
represents:
car
The shared path:
c → a
represents their common prefix.
If you remember "tree of characters", you understand the core idea of a Trie.
Summary
A Trie is a tree-based data structure designed primarily for storing and searching strings.
Key ideas:
- Each node represents a character.
- A path from the root represents a string.
- Common prefixes are shared.
-
isEndOfWordidentifies complete words. - Search takes O(L), where L is the string length.
- Prefix searches are one of its biggest strengths.
- Tries are useful for autocomplete and dictionary-like applications.
- They can consume significant memory.
- Compressed Tries can reduce memory usage.
The most important distinction is:
Hash Table → Exact lookup
Trie → Prefix-aware lookup
Top comments (0)