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 ...
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
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.
isEndOfWord identifies 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