Introduction
When building features like search bar autocomplete, spell checkers, or IP routing tables, traditional hash maps and balanced binary search trees often fall short. While a hash map provides $O(1)$ lookup for exact matches, it fails at prefix matching without scanning every single key. This is where the Trie (pronounced "try"), also known as a prefix tree or digital tree, becomes indispensable.
A Trie is an ordered tree data structure used to store a dynamic set of strings, where the keys are usually strings. Unlike binary search trees, nodes in a Trie do not store the associated key; instead, its position in the tree defines the key with which it is associated. All descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.
TrieNode Structure
At the heart of every Trie lies the TrieNode. Each node typically contains an array or hash map of pointers to its children (representing subsequent characters) and a boolean flag indicating whether the path from the root down to this node forms a complete, valid word.
Here is a robust, production-ready implementation of a TrieNode and the base Trie class in Java:
import java.util.HashMap;
import java.util.Map;
public class Trie {
// Definition of a Trie Node
public static class TrieNode {
// Using a HashMap for flexibility with character sets (e.g., Unicode)
// For pure ASCII lowercase, an array `TrieNode[] children = new TrieNode[26];` is more optimal.
Map<Character, TrieNode> children;
boolean isEndOfWord;
public TrieNode() {
children = new HashMap<>();
isEndOfWord = false;
}
}
private final TrieNode root;
public Trie() {
root = new TrieNode();
}
}
Core Operations
A Trie supports three fundamental operations: Insertion, Search, and Prefix Search (startsWith). All operations operate in $O(m)$ time complexity, where $m$ is the length of the key or prefix, independent of the number of words stored in the Trie.
1. Insertion
To insert a word into a Trie, we iterate through each character of the word. For each character, we check if a child node already exists in the current node's children map. If it does not exist, we create a new TrieNode and insert it. Finally, we mark the node corresponding to the last character as the end of a word.
public void insert(String word) {
if (word == null || word.isEmpty()) {
return;
}
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
// Compute or retrieve child node
current.children.putIfAbsent(ch, new TrieNode());
current = current.children.get(ch);
}
// Mark the end of the inserted word
current.isEndOfWord = true;
}
2. Search
Searching for a complete word involves traversing the Trie character by character. If at any point during the traversal a character's corresponding child node is missing, the word does not exist in the Trie. If we successfully reach the end of the word, we must also verify that isEndOfWord is true (to distinguish between a word and a prefix of a longer word).
public boolean search(String word) {
if (word == null) {
return false;
}
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
return false;
}
current = node;
}
return current.isEndOfWord;
}
3. Prefix Search (startsWith)
Prefix matching is identical to the search operation, except we do not require the final node to have its isEndOfWord flag set to true. As long as the traversal completes successfully without missing links, the prefix exists.
public boolean startsWith(String prefix) {
if (prefix == null) {
return false;
}
TrieNode current = root;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
TrieNode node = current.children.get(ch);
if (node == null) {
return false;
}
current = node;
}
return true;
}
Memory Optimization Techniques
While Tries offer exceptional time complexity, their main drawback is high memory consumption due to node overhead, especially when using hash maps for child pointers or storing large alphabets.
Fixed-Size Arrays for ASCII
If your domain is limited to lowercase English letters (a-z), replacing Map<Character, TrieNode> with a fixed-size array of length 26 eliminates hash map overhead and improves cache locality:
public static class OptimizedTrieNode {
OptimizedTrieNode[] children = new OptimizedTrieNode[26];
boolean isEndOfWord = false;
}
Ternary Search Trees (TST)
When memory is critically constrained and the alphabet is large, consider a Ternary Search Tree. A TST combines the memory efficiency of binary search trees with the explicit prefix capabilities of Tries. Each node contains three pointers (left, equal, right) and a single character, reducing wasted pointer space.
Implementing Autocomplete
An autocomplete engine requires not only finding whether a prefix exists, but also retrieving all valid words that start with that prefix. We can achieve this by traversing to the end of the prefix node, and then performing a Depth-First Search (DFS) to collect all valid words underneath.
import java.util.ArrayList;
import java.util.List;
public List<String> autocomplete(String prefix) {
List<String> results = new ArrayList<>();
TrieNode current = root;
// Traverse to the end of the prefix
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
current = current.children.get(ch);
if (current == null) {
return results; // Prefix not found
}
}
// Perform DFS to collect all words starting from this node
dfs(current, new StringBuilder(prefix), results);
return results;
}
private void dfs(TrieNode node, StringBuilder path, List<String> results) {
if (node.isEndOfWord) {
results.add(path.toString());
}
for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
path.append(entry.getKey());
dfs(entry.getValue(), path, results);
path.deleteCharAt(path.length() - 1); // Backtrack
}
}
Solving Word Search II
A classic application of Tries in algorithmic problem-solving is Word Search II (LeetCode 212). The problem asks us to find all words from a given dictionary that can be formed by sequentially adjacent cells in a 2D board of characters.
Brute-forcing DFS for every single word on the board results in catastrophic time complexity. Instead, we insert all target words into a Trie and perform a single DFS traversal across the grid, pruning paths that do not exist in the Trie.
public class WordSearchII {
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
List<String> result = new ArrayList<>();
int rows = board.length;
int cols = board[0].length;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
dfs(board, r, c, trie.root, result);
}
}
return result;
}
private void dfs(char[][] board, int r, int c, Trie.TrieNode node, List<String> result) {
char ch = board[r][c];
if (ch == '#' || !node.children.containsKey(ch)) {
return;
}
node = node.children.get(ch);
if (node.isEndOfWord) {
result.add(node.word); // Assuming we store the full word at the terminal node for convenience
node.isEndOfWord = false; // Prevent duplicate additions
}
board[r][c] = '#'; // Mark as visited
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length) {
dfs(board, nr, nc, node, result);
}
}
board[r][c] = ch; // Backtrack
}
}
Conclusion
The Trie data structure is a powerful primitive for string-heavy systems and autocomplete features. By trading memory overhead for predictable, prefix-bound runtime complexity ($O(m)$), Tries outperform general-purpose indexing structures in lexicographical domains. When implementing Tries in production, always evaluate your alphabet size to choose between pointer arrays and dynamic maps, and utilize pruning strategies to keep traversal algorithms efficient.
Top comments (0)