🔡 Mastering the Trie (Prefix Tree) in Java
When dealing with problems like autocomplete, spell checking, or prefix-based searches, a standard data structure like HashMap or TreeMap doesn’t cut it. This is where the Trie (pronounced “try”), also known as a prefix tree, shines.
In this post, we’ll cover:
- What a Trie is and why it matters
- Core operations (insert, search, prefix search, delete)
- A clean Java implementation using arrays (
children[26]) - When to use Tries vs HashMaps
📖 What is a Trie?
A Trie is a tree-like data structure used to store strings efficiently.
- Each node represents a character.
- A path from root to a node forms a prefix.
- Nodes can mark the end of a word.
👉 Think of it as a dictionary where words share common prefixes.
Example: inserting "cat", "car", and "cart" results in:
root
|
c
|
a
/
t r
|
t
-
"cat"ends att. -
"car"ends atr. -
"cart"ends at secondt.
⚡ Why Tries?
-
Prefix search is O(L), where
Lis the length of the word. - Eliminates repeated prefixes (saves space in dense datasets).
-
Perfect for:
- Autocomplete
- Dictionary lookups
- Spell checkers
- Word games (Scrabble, Boggle, etc.)
🛠️ Trie Implementation in Java (Array-based)
For performance, we’ll implement the Trie using fixed-size arrays (children[26]), assuming only lowercase English letters (a–z).
public class Trie {
private static class TrieNode {
private final TrieNode[] children = new TrieNode[26];
private boolean isEndOfWord = false;
private boolean containsKey(char ch) {
return children[ch - 'a'] != null;
}
private TrieNode get(char ch) {
return children[ch - 'a'];
}
private void put(char ch, TrieNode node) {
children[ch - 'a'] = node;
}
}
private final TrieNode root;
public Trie() {
this.root = new TrieNode();
}
/** Insert a word into the Trie */
public void insert(String word) {
TrieNode current = root;
for (char ch : word.toCharArray()) {
if (!current.containsKey(ch)) {
current.put(ch, new TrieNode());
}
current = current.get(ch);
}
current.isEndOfWord = true;
}
/** Search for an exact word */
public boolean search(String word) {
TrieNode node = findNode(word);
return node != null && node.isEndOfWord;
}
/** Check if any word starts with the given prefix */
public boolean startsWith(String prefix) {
return findNode(prefix) != null;
}
/** Delete a word from the Trie */
public boolean delete(String word) {
return delete(root, word, 0);
}
private boolean delete(TrieNode current, String word, int index) {
if (index == word.length()) {
if (!current.isEndOfWord) return false;
current.isEndOfWord = false;
return isEmpty(current);
}
char ch = word.charAt(index);
TrieNode node = current.get(ch);
if (node == null) return false;
boolean shouldDelete = delete(node, word, index + 1);
if (shouldDelete) {
current.put(ch, null);
return isEmpty(current) && !current.isEndOfWord;
}
return false;
}
private boolean isEmpty(TrieNode node) {
for (TrieNode child : node.children) {
if (child != null) return false;
}
return true;
}
private TrieNode findNode(String str) {
TrieNode current = root;
for (char ch : str.toCharArray()) {
current = current.get(ch);
if (current == null) return null;
}
return current;
}
}
📊 Example Usage
public class TrieDemo {
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("cart");
System.out.println(trie.search("car")); // true
System.out.println(trie.search("cat")); // true
System.out.println(trie.startsWith("ca")); // true
System.out.println(trie.search("cap")); // false
trie.delete("car");
System.out.println(trie.search("car")); // false
System.out.println(trie.search("cart")); // true
}
}
🔄 Array vs HashMap Implementation
| Aspect | Array-based (children[26]) |
HashMap-based |
|---|---|---|
| Speed | O(1) (direct index lookup) | O(1) average, slower due to hashing |
| Memory | Higher (26 slots per node) | Lower for sparse tries |
| Flexibility | Only a–z lowercase |
Any charset (Unicode, upper/lower) |
| Use Case | Dictionaries, autocomplete, word games | General-purpose, multilingual |
✅ Key Takeaways
- Tries are prefix-optimized trees that outperform maps in prefix-heavy workloads.
- Array-based implementation is faster, but HashMap-based is more flexible.
- Perfect use cases: autocomplete, spell checkers, and word search problems.
⚡ That’s it! You now have a production-grade Trie in Java.
If you’re building search-heavy apps, autocomplete features, or game engines — a Trie is your new best friend.
