Introduction to the Trie Data Structure
A Trie (pronounced "try") is a tree-like data structure that stores a dynamic set of strings in a way that facilitates fast retrieval. The name comes from the word "retrieval," which gives us a clue about its primary purpose. Unlike a binary search tree where comparisons are made between entire keys, a Trie breaks keys down into individual characters. Each node in a Trie represents a single character, and paths from the root to leaf nodes spell out entire words.
The core idea is deceptively simple: instead of storing strings as monolithic entities, we store them character by character along shared paths. Words like "car", "cat", and "cart" share the prefix "ca", so they branch off from a common ancestor node representing 'a'. This structural sharing is what gives the Trie its power—it compresses common prefixes and enables prefix-based queries that would be expensive or impossible with hash tables or binary search trees.
A typical Trie node contains two essential components:
- A map or array of child references — one for each possible character
- A boolean flag (or counter) — indicating whether a complete word ends at that node
Optionally, nodes may store additional metadata such as word frequency counts, values for key-value storage, or references to full words for quick retrieval.
Why Tries Matter
🚀 Deploy your AI agent in 10 minutes
Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.
Try it free →Tries solve a specific class of problems that other data structures handle poorly. Consider these real-world scenarios:
- Autocomplete / Typeahead — When a user types "hel", the system must instantly suggest "hello", "help", "helmet". A Trie can return all words with a given prefix in O(k + m) time where k is the prefix length and m is the number of matches, while a hash table would need to scan all keys.
- Spell Checkers — Quickly verify if a word exists in a dictionary and suggest corrections by traversing nearby paths.
- IP Routing Tables — Longest prefix matching is the backbone of internet routing. Tries (specifically Patricia Tries) excel at this.
- Genome Analysis — Storing and querying DNA sequences where prefixes correspond to gene markers.
- Word Games — Boggle, Scrabble, and crossword solvers use Tries for rapid dictionary lookups by prefix.
The key advantage is that insertion, deletion, and lookup all operate in O(L) time, where L is the length of the key, independent of the total number of keys stored. This makes Tries particularly valuable when you have a large corpus and need fast prefix operations.
Core Operations
Before diving into implementations, let's understand the four fundamental operations that every Trie must support:
1. Insertion
Starting at the root, iterate through each character of the word. For each character, check if a child node exists. If not, create one. Move to that child and continue. After processing the final character, mark the current node as the end of a word (set a boolean flag or increment a counter).
2. Search (Exact Match)
Starting at the root, follow the path defined by each character. If at any point the required child node doesn't exist, the word is not in the Trie. If you reach the end of the word, check if the final node is marked as an end-of-word. Only return true if the end-of-word flag is set—otherwise the path exists as a prefix of another word but not as a complete word itself.
3. Prefix Search (Starts With)
Similar to exact search, but we only care whether the prefix path exists, regardless of end-of-word flags. If we can traverse all characters of the prefix without missing any child nodes, the Trie contains at least one word with that prefix.
4. Deletion
Deletion is more nuanced. For a simple implementation, you can unmark the end-of-word flag. For a memory-efficient implementation, you should recursively prune nodes that no longer have children and are not end-of-word markers for other words. This bottom-up cleanup prevents memory leaks in long-running applications.
Implementation Approaches
There are several distinct ways to implement a Trie, each with different trade-offs between memory usage, speed, and flexibility. We'll explore four complete solutions:
- Array-Based Fixed Trie — Uses a fixed-size array of child pointers (e.g., size 26 for lowercase English). Extremely fast, simple, but memory-hungry for sparse alphabets.
- HashMap-Based Dynamic Trie — Uses a hash map for children, supporting arbitrary character sets (Unicode) with memory proportional to actual branching factor.
- Word-Storing Trie — Stores complete words at end-of-word nodes for fast retrieval without reconstruction.
- Recursive Trie — Demonstrates elegant recursive algorithms for operations, useful in functional programming contexts.
Solution 1: Array-Based Trie Node
This is the classic implementation for scenarios where the alphabet is constrained—typically lowercase English letters 'a' through 'z'. Each node holds an array of 26 child pointers (or indices). This approach delivers maximum speed because child lookup is a direct array access, but it wastes memory when the alphabet is sparsely used.
Node Structure
public class ArrayTrieNode {
// Array of 26 children, one for each lowercase letter
ArrayTrieNode[] children;
boolean isEndOfWord;
// Optional: count of words that pass through this node
int prefixCount;
public ArrayTrieNode() {
children = new ArrayTrieNode[26];
isEndOfWord = false;
prefixCount = 0;
}
// Check if a character has a child node
public boolean containsKey(char ch) {
int index = ch - 'a';
return children[index] != null;
}
// Get the child node for a character
public ArrayTrieNode get(char ch) {
int index = ch - 'a';
return children[index];
}
// Create and set a child node for a character
public void put(char ch, ArrayTrieNode node) {
int index = ch - 'a';
children[index] = node;
}
}
Complete Array-Based Trie Class
public class ArrayTrie {
private ArrayTrieNode root;
public ArrayTrie() {
root = new ArrayTrieNode();
}
/**
* Insert a word into the Trie.
* Time Complexity: O(L) where L is word length
* Space Complexity: O(L) for new nodes created
*/
public void insert(String word) {
ArrayTrieNode current = root;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
if (!current.containsKey(ch)) {
current.put(ch, new ArrayTrieNode());
}
current = current.get(ch);
current.prefixCount++;
}
current.isEndOfWord = true;
}
/**
* Search for an exact word match.
* Time Complexity: O(L)
*/
public boolean search(String word) {
ArrayTrieNode node = searchNode(word);
return node != null && node.isEndOfWord;
}
/**
* Check if any word starts with the given prefix.
* Time Complexity: O(P) where P is prefix length
*/
public boolean startsWith(String prefix) {
return searchNode(prefix) != null;
}
/**
* Count how many words start with the given prefix.
* Uses the prefixCount field for O(P) lookup.
*/
public int countWordsWithPrefix(String prefix) {
ArrayTrieNode node = searchNode(prefix);
return node != null ? node.prefixCount : 0;
}
// Helper: traverse to the node representing a string, return null if path doesn't exist
private ArrayTrieNode searchNode(String str) {
ArrayTrieNode current = root;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (!current.containsKey(ch)) {
return null;
}
current = current.get(ch);
}
return current;
}
/**
* Delete a word from the Trie with recursive pruning.
* Returns true if the word was found and deleted.
*/
public boolean delete(String word) {
return deleteRecursive(root, word, 0);
}
private boolean deleteRecursive(ArrayTrieNode current, String word, int depth) {
// Base case: reached end of word
if (depth == word.length()) {
if (!current.isEndOfWord) {
return false; // Word doesn't exist
}
current.isEndOfWord = false;
// Return true if node has no children (can be pruned)
return hasNoChildren(current);
}
char ch = word.charAt(depth);
int index = ch - 'a';
if (current.children[index] == null) {
return false; // Path doesn't exist
}
// Recurse to child
boolean shouldPruneChild = deleteRecursive(current.children[index], word, depth + 1);
if (shouldPruneChild) {
current.children[index] = null;
current.prefixCount--;
// Return true if this node is now deletable
return !current.isEndOfWord && hasNoChildren(current);
}
return false;
}
private boolean hasNoChildren(ArrayTrieNode node) {
for (ArrayTrieNode child : node.children) {
if (child != null) return false;
}
return true;
}
}
Usage Example
public static void main(String[] args) {
ArrayTrie trie = new ArrayTrie();
trie.insert("apple");
trie.insert("app");
trie.insert("apricot");
trie.insert("banana");
System.out.println(trie.search("app")); // true
System.out.println(trie.search("appl")); // false (not a complete word)
System.out.println(trie.startsWith("app")); // true
System.out.println(trie.startsWith("ban")); // true
System.out.println(trie.startsWith("cat")); // false
System.out.println(trie.countWordsWithPrefix("app")); // 2 (app, apple)
trie.delete("app");
System.out.println(trie.search("app")); // false
System.out.println(trie.search("apple")); // true (still exists)
}
Solution 2: HashMap-Based Dynamic Trie
When your character set is unbounded—think Unicode strings, mixed case, symbols, or emoji—a fixed array becomes impractical. The HashMap-based approach stores only the branches that actually exist, dramatically reducing memory for sparse tries while maintaining O(1) expected child lookup time.
Node Structure
import java.util.HashMap;
import java.util.Map;
public class HashMapTrieNode {
Map<Character, HashMapTrieNode> children;
boolean isEndOfWord;
// Track the actual character for easier debugging
char content;
public HashMapTrieNode(char content) {
this.children = new HashMap<>();
this.isEndOfWord = false;
this.content = content;
}
// Convenience method for root node (no character)
public HashMapTrieNode() {
this.children = new HashMap<>();
this.isEndOfWord = false;
}
}
Complete HashMap-Based Trie Class
import java.util.*;
public class HashMapTrie {
private HashMapTrieNode root;
public HashMapTrie() {
root = new HashMapTrieNode();
}
/**
* Insert a word. Supports any Unicode characters.
*/
public void insert(String word) {
HashMapTrieNode current = root;
for (char ch : word.toCharArray()) {
current.children.putIfAbsent(ch, new HashMapTrieNode(ch));
current = current.children.get(ch);
}
current.isEndOfWord = true;
}
/**
* Exact word search.
*/
public boolean search(String word) {
HashMapTrieNode node = traverse(word);
return node != null && node.isEndOfWord;
}
/**
* Prefix search.
*/
public boolean startsWith(String prefix) {
return traverse(prefix) != null;
}
/**
* Collect all words that start with a given prefix.
* Demonstrates the power of Trie for autocomplete.
*/
public List<String> getWordsWithPrefix(String prefix) {
List<String> result = new ArrayList<>();
HashMapTrieNode startNode = traverse(prefix);
if (startNode == null) {
return result;
}
StringBuilder sb = new StringBuilder(prefix);
collectWords(startNode, sb, result);
return result;
}
/**
* Get all words stored in the Trie.
*/
public List<String> getAllWords() {
return getWordsWithPrefix("");
}
private void collectWords(HashMapTrieNode node, StringBuilder currentWord, List<String> result) {
if (node.isEndOfWord) {
result.add(currentWord.toString());
}
for (Map.Entry<Character, HashMapTrieNode> entry : node.children.entrySet()) {
currentWord.append(entry.getKey());
collectWords(entry.getValue(), currentWord, result);
currentWord.deleteCharAt(currentWord.length() - 1); // backtrack
}
}
/**
* Delete with full pruning.
*/
public boolean delete(String word) {
// Stack to track the path for bottom-up pruning
Deque<HashMapTrieNode> stack = new ArrayDeque<>();
Deque<Character> charStack = new ArrayDeque<>();
HashMapTrieNode current = root;
for (char ch : word.toCharArray()) {
if (!current.children.containsKey(ch)) {
return false; // Word doesn't exist
}
stack.push(current);
charStack.push(ch);
current = current.children.get(ch);
}
if (!current.isEndOfWord) {
return false;
}
// Unmark end-of-word
current.isEndOfWord = false;
// Prune from bottom up
while (!stack.isEmpty() && current.children.isEmpty() && !current.isEndOfWord) {
HashMapTrieNode parent = stack.pop();
char charToRemove = charStack.pop();
parent.children.remove(charToRemove);
current = parent;
}
return true;
}
private HashMapTrieNode traverse(String str) {
HashMapTrieNode current = root;
for (char ch : str.toCharArray()) {
if (!current.children.containsKey(ch)) {
return null;
}
current = current.children.get(ch);
}
return current;
}
/**
* Count total nodes (useful for memory analysis).
*/
public int countNodes() {
return countNodesRecursive(root);
}
private int countNodesRecursive(HashMapTrieNode node) {
int count = 1;
for (HashMapTrieNode child : node.children.values()) {
count += countNodesRecursive(child);
}
return count;
}
}
Usage Example with Unicode
public static void main(String[] args) {
HashMapTrie trie = new HashMapTrie();
trie.insert("café");
trie.insert("café au lait");
trie.insert("café crème");
trie.insert("hello");
trie.insert("hello world");
trie.insert("Hello");
trie.insert("HelloWorld");
// Autocomplete for "café"
List<String> suggestions = trie.getWordsWithPrefix("café");
System.out.println("Suggestions for 'café': " + suggestions);
// Output: [café, café au lait, café crème]
// Unicode prefix search
System.out.println(trie.startsWith("Hello")); // true
// Get all words
System.out.println("All words: " + trie.getAllWords());
// Delete and verify
trie.delete("café");
System.out.println(trie.search("café")); // false
System.out.println(trie.search("café au lait")); // true (still exists)
System.out.println("Total nodes: " + trie.countNodes());
}
Solution 3: Trie with Word Storage
For autocomplete applications, reconstructing words by traversing from the root to each leaf can be expensive. An optimization is to store the complete word (or suffix) directly at end-of-word nodes. This eliminates backtracking during collection and is particularly valuable when the Trie is deep.
Complete Word-Storing Trie
import java.util.*;
public class WordStoringTrie {
class Node {
Map<Character, Node> children = new HashMap<>();
boolean isWord;
String storedWord; // Complete word at this node
int frequency; // Optional: word frequency for ranking suggestions
Node() {}
}
private Node root;
public WordStoringTrie() {
root = new Node();
}
/**
* Insert with full word storage.
*/
public void insert(String word) {
insert(word, 1);
}
public void insert(String word, int frequency) {
Node current = root;
for (char ch : word.toCharArray()) {
current.children.putIfAbsent(ch, new Node());
current = current.children.get(ch);
}
current.isWord = true;
current.storedWord = word;
current.frequency = frequency;
}
/**
* Get autocomplete suggestions ranked by frequency.
* Returns up to 'limit' most frequent words with given prefix.
*/
public List<String> autocomplete(String prefix, int limit) {
List<String> results = new ArrayList<>();
Node startNode = traverse(prefix);
if (startNode == null) {
return results;
}
// Use priority queue to rank by frequency
PriorityQueue<Node> pq = new PriorityQueue<>(
(a, b) -> Integer.compare(b.frequency, a.frequency)
);
collectNodes(startNode, pq);
while (!pq.isEmpty() && results.size() < limit) {
Node node = pq.poll();
if (node.isWord) {
results.add(node.storedWord);
}
}
return results;
}
private void collectNodes(Node node, PriorityQueue<Node> pq) {
if (node.isWord) {
pq.offer(node);
}
for (Node child : node.children.values()) {
collectNodes(child, pq);
}
}
/**
* Fuzzy search: find words within edit distance 1.
* Useful for spell checking.
*/
public Set<String> fuzzySearch(String word, int maxEdits) {
Set<String> results = new HashSet<>();
fuzzySearchRecursive(root, word, 0, new StringBuilder(), 0, maxEdits, results);
return results;
}
private void fuzzySearchRecursive(Node node, String word, int depth,
StringBuilder current, int edits,
int maxEdits, Set<String> results) {
if (edits > maxEdits) return;
if (depth == word.length()) {
if (node.isWord && edits <= maxEdits) {
results.add(node.storedWord);
}
// Allow extra characters (insertion at end)
for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
current.append(entry.getKey());
fuzzySearchRecursive(entry.getValue(), word, depth,
current, edits + 1, maxEdits, results);
current.deleteCharAt(current.length() - 1);
}
return;
}
char targetChar = word.charAt(depth);
// Exact match (no edit)
if (node.children.containsKey(targetChar)) {
current.append(targetChar);
fuzzySearchRecursive(node.children.get(targetChar), word, depth + 1,
current, edits, maxEdits, results);
current.deleteCharAt(current.length() - 1);
}
// Substitution
for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
if (entry.getKey() != targetChar) {
current.append(entry.getKey());
fuzzySearchRecursive(entry.getValue(), word, depth + 1,
current, edits + 1, maxEdits, results);
current.deleteCharAt(current.length() - 1);
}
}
// Deletion (skip current character in word)
fuzzySearchRecursive(node, word, depth + 1, current, edits + 1, maxEdits, results);
// Insertion (extra character from trie, keep word pointer same)
for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
current.append(entry.getKey());
fuzzySearchRecursive(entry.getValue(), word, depth,
current, edits + 1, maxEdits, results);
current.deleteCharAt(current.length() - 1);
}
}
public boolean search(String word) {
Node node = traverse(word);
return node != null && node.isWord;
}
public boolean startsWith(String prefix) {
return traverse(prefix) != null;
}
private Node traverse(String str) {
Node current = root;
for (char ch : str.toCharArray()) {
if (!current.children.containsKey(ch)) {
return null;
}
current = current.children.get(ch);
}
return current;
}
}
Demonstration
public static void main(String[] args) {
WordStoringTrie trie = new WordStoringTrie();
trie.insert("apple", 100);
trie.insert("app", 50);
trie.insert("application", 80);
trie.insert("apricot", 30);
trie.insert("apply", 60);
trie.insert("banana", 90);
trie.insert("band", 40);
trie.insert("bandana", 20);
// Top 3 autocomplete suggestions for "app"
List<String> suggestions = trie.autocomplete("app", 3);
System.out.println("Top suggestions for 'app': " + suggestions);
// Output: [apple, application, apply] (ranked by frequency)
// Fuzzy search for misspelled "aple" (should find "apple")
Set<String> fuzzyResults = trie.fuzzySearch("aple", 1);
System.out.println("Fuzzy matches for 'aple': " + fuzzyResults);
// Output: [apple] (1 substitution)
}
Solution 4: Recursive Trie Implementation
While iterative solutions are generally preferred for production (stack depth concerns), a recursive implementation offers elegance and clarity. It's particularly useful in functional programming languages or when teaching the conceptual model. Here's a clean recursive Trie in Java using a functional style with immutable-like patterns.
Recursive Trie
import java.util.*;
public class RecursiveTrie {
static class Node {
Map<Character, Node> children;
boolean isEndOfWord;
Node() {
children = new HashMap<>();
isEndOfWord = false;
}
Node(Map<Character, Node> children, boolean isEndOfWord) {
this.children = children;
this.isEndOfWord = isEndOfWord;
}
}
private Node root;
public RecursiveTrie() {
root = new Node();
}
/**
* Recursively insert a word.
*/
public void insert(String word) {
root = insertRecursive(root, word, 0);
}
private Node insertRecursive(Node node, String word, int index) {
if (index == word.length()) {
// Create new node with isEndOfWord = true, preserving children
return new Node(node.children, true);
}
char ch = word.charAt(index);
Node child = node.children.getOrDefault(ch, new Node());
Node updatedChild = insertRecursive(child, word, index + 1);
Map<Character, Node> newChildren = new HashMap<>(node.children);
newChildren.put(ch, updatedChild);
return new Node(newChildren, node.isEndOfWord);
}
/**
* Recursive search.
*/
public boolean search(String word) {
return searchRecursive(root, word, 0);
}
private boolean searchRecursive(Node node, String word, int index) {
if (index == word.length()) {
return node.isEndOfWord;
}
char ch = word.charAt(index);
Node child = node.children.get(ch);
if (child == null) {
return false;
}
return searchRecursive(child, word, index + 1);
}
/**
* Recursive prefix check.
*/
public boolean startsWith(String prefix) {
return startsWithRecursive(root, prefix, 0);
}
private boolean startsWithRecursive(Node node, String prefix, int index) {
if (index == prefix.length()) {
return true;
}
char ch = prefix.charAt(index);
Node child = node.children.get(ch);
if (child == null) {
return false;
}
return startsWithRecursive(child, prefix, index + 1);
}
/**
* Recursively collect all words with a prefix.
*/
public List<String> wordsWithPrefix(String prefix) {
List<String> results = new ArrayList<>();
Node startNode = traverseToNode(root, prefix, 0);
if (startNode != null) {
collectWordsRecursive(startNode, new StringBuilder(prefix), results);
}
return results;
}
private Node traverseToNode(Node node, String prefix, int index) {
if (index == prefix.length()) {
return node;
}
char ch = prefix.charAt(index);
Node child = node.children.get(ch);
if (child == null) return null;
return traverseToNode(child, prefix, index + 1);
}
private void collectWordsRecursive(Node node, StringBuilder currentWord, List<String> results) {
if (node.isEndOfWord) {
results.add(currentWord.toString());
}
for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
currentWord.append(entry.getKey());
collectWordsRecursive(entry.getValue(), currentWord, results);
currentWord.deleteCharAt(currentWord.length() - 1);
}
}
/**
* Recursive delete that returns a new root (functional style).
*/
public boolean delete(String word) {
if (!search(word)) return false;
root = deleteRecursive(root, word, 0);
return true;
}
private Node deleteRecursive(Node node, String word, int index) {
if (index == word.length()) {
return new Node(node.children, false);
}
char ch = word.charAt(index);
Node child = node.children.get(ch);
if (child == null) return node; // shouldn't happen if search passed
Node updatedChild = deleteRecursive(child, word, index + 1);
Map<Character, Node> newChildren = new HashMap<>(node.children);
// Prune if child has no children and isn't a word end
if (updatedChild.children.isEmpty() && !updatedChild.isEndOfWord) {
newChildren.remove(ch);
} else {
newChildren.put(ch, updatedChild);
}
return new Node(newChildren, node.isEndOfWord);
}
}
Complexity Analysis
Understanding the performance characteristics of Trie operations is essential for making informed architectural decisions. Here's a detailed breakdown for each implementation approach:
Time Complexity
- Insertion: O(L) — Where L is the length of the word. Each character requires a constant-time operation: array index or hash map lookup. For the fixed-array implementation, it's strictly O(L) with a very small constant factor. For HashMap, it's amortized O(L) due to occasional hash map resizing.
- Search (Exact): O(L) — Same traversal as insertion. The final check of the end-of-word flag is O(1).
- Prefix Search (startsWith): O(P) — Where P is the length of the prefix. We only traverse P characters regardless of how many words share that prefix.
- Autocomplete / Collect All Words with Prefix: O(P + K*L_avg) — Where K is the number of matching words. We first traverse P characters to reach the prefix node, then perform DFS/BFS through all descendant paths. In the worst case (prefix is empty string), this visits all N nodes in the Trie.
- Deletion: O(L) — In the pruning version, we traverse down L characters and then potentially back up L characters to prune empty branches. Total operations are bounded by 2L.
Space Complexity
- Array-Based Trie: O(N * 26) = O(N) — Where N is the total number of nodes. Each node allocates a 26-element array of pointers (typically 8 bytes each on 64-bit JVM), resulting in ~208 bytes per node plus object overhead. For a dictionary of 100,000 English words averaging 8 characters, you might have ~250,000 nodes consuming ~60 MB. This is the memory-inefficient extreme.
- HashMap-Based Trie: O(N * branching_factor) — Each node only stores pointers for characters that actually appear in its children. For English text, the average branching factor is much less than 26 (typically 3-8 after the first few levels). A node with 4 children might use ~100 bytes including HashMap overhead. For the same 100,000-word dictionary, memory consumption drops to ~25-35 MB.
- Word-Storing Trie: O(N * branching_factor + W) — Additional W storage where W is the sum of all stored word lengths. Each word is stored once at its terminal node, adding roughly 2 bytes per character (compressed strings in Java) plus String object overhead.
Comparison with Alternative Data Structures
Operation | Trie | Hash Table | Binary Search Tree
-----------------------|---------------|---------------|--------------------
Insert | O(L) | O(L) avg | O(L * log N)
Search Exact | O(L) | O(L) avg | O(L * log N)
Search Prefix | O(P) | O(N) scan | O(N) scan
Autocomplete (top K) | O(P + matches)| O(N) full scan| O(N) full scan
Longest Prefix Match | O(L) | Not supported | Not supported
Space Efficiency | Moderate | Excellent | Good
The Trie's killer feature is prefix operations. If your application doesn't need prefix search, a hash table is almost always the better choice due to simpler implementation and lower memory overhead. But once prefix queries enter the picture, the Trie becomes irreplaceable.
Best Practices and Advanced Considerations
1. Choose the Right Alphabet Strategy
For constrained alphabets (lowercase English, DNA bases, binary), use a fixed array. The speed improvement is measurable in high-throughput scenarios. For anything involving user-generated text, Unicode, or mixed case, use HashMap. A hybrid approach uses an array for the first few levels (where branching is high) and switches to sparse representations deeper in the tree.
2. Thread Safety
Standard Trie implementations are not thread-safe. For concurrent read-heavy workloads, consider:
- Immutable Tries — Build the Trie once, then share it across threads. Reads require no synchronization.
- ConcurrentHashMap for children — Allows concurrent insertions and reads, though end-of-word flag updates need atomic operations (AtomicBoolean or synchronized blocks).
- Read-Write Locks — Acceptable for moderate write contention.
3. Memory Optimization Techniques
- Node Pooling — Allocate nodes in contiguous arrays and use integer indices instead of references. This reduces memory fragmentation and object overhead.
- Compressed Paths (Radix Tree) — When a node has only one child, merge it with that child into a single node storing a multi-character string. This dramatically reduces node count for sparse dictionaries.
- Lazy Allocation — Delay creating child arrays/maps until a character is actually inserted. The root node might start with null children and only allocate on first insert.
- Custom Compact Maps — Instead of full HashMap, use a small sorted array of character-node pairs for nodes with few children. Linear scan beats HashMap overhead