Prefix Trees
Overview
A Trie (pronounced 'try', short for reTRIEval tree), also known as a Prefix Tree, is a specialized tree designed explicitly for storing and searching strings.
In a standard BST or HashMap, searching for a string like 'apple' takes time proportional to the number of elements in the structure. In a Trie, the search time depends ONLY on the length of the string itself (O(L)), completely independent of how many millions of words the tree holds.
A Trie stores characters in its nodes. The root is empty, and its children represent the first character of words. A path down the tree spells out a word. Because words with the same prefix (e.g., 'car', 'card', 'cart') share the same nodes for 'c', 'a', and 'r', Tries are incredibly space-efficient for dictionaries and are the ultimate data structure for autocomplete and spell-checking systems.
Syntax
public class Trie {
static class TrieNode {
// Array of 26 pointers for lowercase English letters
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false; // True if a word ends at this node
}
TrieNode root = new TrieNode();
// O(L) Insertion, where L is word length
public void insert(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a'; // Convert 'a'->0, 'b'->1, etc.
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index]; // Move down the tree
}
current.isEndOfWord = true; // Mark the final node
}
// O(L) Search for an exact word
public boolean search(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
return false; // Path breaks, word doesn't exist
}
current = current.children[index];
}
return current.isEndOfWord; // Must be marked as an end!
}
}Common Pitfalls
- Assuming a matching prefix means a matching word. If you insert 'apple', the tree contains nodes for 'a-p-p-l-e'. If you search for 'app', the path exists, but 'app' is NOT a word. You must check
if (current.isEndOfWord)at the final node. - Hardcoding array sizes poorly. Using
TrieNode[26]is highly optimized but ONLY works for lowercase English letters (a-z). If you need uppercase, numbers, or symbols, you must use aHashMap<Character, TrieNode>instead, which slightly increases overhead. - High memory consumption for sparse datasets. If your dataset has very few shared prefixes, the Trie will create millions of objects. Each Node in Java has memory overhead, making an array-based Trie a memory hog if not carefully managed.
Interview Questions
A HashMap is great for exact matches, but it cannot answer 'Give me all words starting with 'auto''. A Trie inherently groups words by their prefixes, making autocomplete searches (Prefix Matching) highly efficient. Additionally, for a dense dictionary, a Trie saves memory because common prefixes are shared.
First, traverse the Trie using the characters of the user's input prefix. Once you reach the node representing the last character of the prefix, perform a Depth-First Search (DFS) from that node downwards to collect all nodes marked isEndOfWord. These represent the autocomplete suggestions.
Real-World Example
Google's Search Bar Autocomplete is heavily reliant on distributed Trie-like structures. When you type 'how to co', the system instantly traverses to the 'o' node under 'c' under ' ' under 'o', etc., and returns the most popular paths ('how to code', 'how to cook').
public List<String> autocomplete(String prefix) {
List<String> results = new ArrayList<>();
TrieNode current = root;
// 1. Navigate to the end of the prefix
for (char c : prefix.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) return results; // No matches
current = current.children[index];
}
// 2. DFS to find all words branching from here
dfsFindWords(current, prefix, results);
return results;
}
private void dfsFindWords(TrieNode node, String prefixSoFar, List<String> results) {
if (node.isEndOfWord) results.add(prefixSoFar);
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
char nextChar = (char) (i + 'a');
dfsFindWords(node.children[i], prefixSoFar + nextChar, results);
}
}
}Check Your Knowledge
Test your understanding of Prefix Trees with these quick questions.