Prefix Trees
Overview
A Trie (pronounced 'try') is a highly specialized tree designed specifically for searching strings and prefixes. Instead of storing entire words in a node, each node stores a single character. Words are formed by traversing down the branches. If you have 10,000 words that start with 'Auto', a Trie only stores the 'A-u-t-o' branch once. It provides blindingly fast O(L) lookup times (where L is the length of the word), heavily outperforming HashMaps for prefix-matching tasks like Autocomplete.
Syntax
Each node acts as an array of 26 possible paths. If a path is not null, it means that letter exists in the sequence.
class TrieNode {
// Array holds 26 pointers for lowercase English letters
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false;
public TrieNode() {}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
}Insertion and search only take time proportional to the length of the word being inserted, entirely independent of how many millions of words are stored in the tree!
public void insert(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a'; // Convert 'a'-'z' to 0-25
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isEndOfWord = true; // Mark the end
}
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; // The prefix exists!
}Common Pitfalls
- Massive memory consumption. If you are storing alphanumeric characters plus symbols, your array size jumps from 26 to 256 or more per node, exploding memory usage. Consider using HashMaps inside the nodes instead of Arrays.
- Forgetting to set `isEndOfWord = true` during insertion.
Interview Tips
- Tries provide blindingly fast O(L) lookups (L = word length) completely independent of how many millions of words are stored in the tree.
Real-World Example
Google Search Autocomplete, Spell Checkers, and IP Routing tables in networking routers.
public class SearchEngine {
Trie dictionary = new Trie();
public void addDocumentWord(String word) {
dictionary.insert(word);
}
public List<String> getAutocompleteSuggestions(String prefix) {
// Find the node where the prefix ends, then run DFS
// to gather all 'isEndOfWord' paths below it.
return findWordsFromPrefixNode(prefix);
}
}