Definition
- Trie pattern – a design pattern using a prefix tree to efficiently handle word insertion, exact lookup, and prefix matching.
- Edge characters – each edge in the tree carries one character; a root-to-node path spells a prefix.
- End-of-word flag – a boolean on each node marking whether a complete word terminates there.
- Shared prefixes – words sharing a prefix share the same initial path, saving space.
- Key-length operations – insert, search, and startsWith all run in O(L) time where L is the key length.
The National Bank of India stores a large set of registered merchant names and wants to look up names and check prefixes quickly as a teller types. A trie stores shared prefixes once, so RELIANCE and RELIABLE share the same early branch, making both exact lookups and prefix autocomplete fast.
Understanding the Concepts
What is the Trie Pattern?
The Trie pattern uses a prefix tree (trie) as the core data structure for problems involving word storage, exact-word lookup, and prefix matching. The pattern appears in autocomplete systems, spell checkers, word games, and IP routing tables.
The trie is a tree where each edge carries one character. A path from the root spells a prefix. Shared prefixes are stored once, so "RELIANCE" and "RELIABLE" share the path R-E-L-I-A.
How do you implement the Trie pattern?
The implementation has three methods: insert, search, and startsWith. All three share a common traversal helper that walks the trie character by character.
package com.bank.service;
import java.util.HashMap;
import java.util.Map;
public class MerchantNameTrie {
private static class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isWord = false;
}
private final TrieNode root = new TrieNode();
public void insert(String name) {
TrieNode node = root;
for (char c : name.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
}
node.isWord = true;
}
public boolean search(String name) {
TrieNode node = traverse(name);
return node != null && node.isWord;
}
public boolean startsWith(String prefix) {
return traverse(prefix) != null;
}
private TrieNode traverse(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.get(c);
if (node == null) return null;
}
return node;
}
public static void main(String[] args) {
MerchantNameTrie trie = new MerchantNameTrie();
trie.insert("RELIANCE");
trie.insert("RELIABLE");
trie.insert("HDFC");
System.out.println("Search RELIANCE: " + trie.search("RELIANCE"));
System.out.println("Search RELI: " + trie.search("RELI"));
System.out.println("Prefix RELI: " + trie.startsWith("RELI"));
System.out.println("Prefix ICICI: " + trie.startsWith("ICICI"));
}
}
Search RELIANCE: true
Search RELI: false
Prefix RELI: true
Prefix ICICI: false
How does the shared-prefix property save space?
Without a trie, storing "RELIANCE" and "RELIABLE" requires 16 characters total. In a trie, the shared prefix "RELIA" is stored once as five nodes, and only the suffixes "NCE" and "BLE" branch. This saving grows with the number of words sharing prefixes.
// Trie structure after inserting RELIANCE and RELIABLE:
// R -> E -> L -> I -> A -> N -> C -> E*
// |-> B -> L -> E*
// 5 shared nodes + 3 + 3 = 11 nodes total, not 16
// (* marks isWord = true)
How is this different from a HashMap-based dictionary?
| Aspect | Trie | HashMap
|---|---|---|
| Exact lookup | O(L) | O(L) average |
| Prefix query | O(L) | O(N) scan all keys |
| Autocomplete | Walk prefix node, DFS children | Not supported efficiently |
| Memory | Higher per-node overhead | Lower for exact lookups |
| Sorted iteration | Lexicographic via DFS | No ordering |
// HashMap: prefix query requires scanning every key
Map<String, Boolean> merchants = new HashMap<>();
merchants.put("RELIANCE", true);
merchants.put("RELIABLE", true);
// Find all starting with "RELI": must scan all entries O(N)
How do you implement autocomplete with a trie?
To autocomplete a prefix, walk to the prefix node, then run a DFS from that node to collect all complete words below it.
import java.util.ArrayList;
import java.util.List;
public List<String> autocomplete(String prefix) {
List<String> results = new ArrayList<>();
TrieNode node = traverse(prefix);
if (node == null) return results;
collectWords(node, new StringBuilder(prefix), results);
return results;
}
private void collectWords(TrieNode node, StringBuilder path, List<String> results) {
if (node.isWord) results.add(path.toString());
for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) {
path.append(entry.getKey());
collectWords(entry.getValue(), path, results);
path.deleteCharAt(path.length() - 1);
}
}
What are the edge cases?
- Empty string insertion – sets root.isWord = true; search("") returns true.
- Single character words – handled correctly by a one-step walk.
- Word that is a prefix of another – "REL" inserted, then "RELIANCE"; search("REL") returns true, startsWith("REL") also true.
- Case sensitivity – "reliance" and "RELIANCE" are different keys unless normalised.
// Inserting a word that is a prefix of an existing word
trie.insert("REL");
System.out.println(trie.search("REL")); // true (isWord set)
System.out.println(trie.search("RELIANCE")); // still true
What are common mistakes?
The most common mistake is confusing search and startsWith by not checking the isWord flag.
// WRONG: search returns true for prefixes
public boolean searchBuggy(String name) {
return traverse(name) != null; // missing isWord check
}
// searchBuggy("RELI") returns true even though "RELI" was never inserted
// CORRECT:
public boolean search(String name) {
TrieNode node = traverse(name);
return node != null && node.isWord;
}
What is the time and space complexity?
Each operation (insert, search, startsWith) runs in O(L) time where L is the key length. Space is O(sum of all inserted character counts) in the worst case. Autocomplete adds O(number of matching words * average word length) for the DFS.
For a banking merchant registry with 50,000 names averaging 12 characters, the trie uses up to 600,000 nodes. Each node with a HashMap child carries some overhead, but the prefix sharing typically reduces this significantly.
What should a senior engineer know?
A senior engineer should know the Trie pattern's real-world applications: autocomplete, spell checking, longest prefix matching in IP routing, and word search in matrices. They should know that in production, a compressed trie (radix tree) merges single-child chains, and that array-based children are faster for fixed small alphabets.
They should also know that the Trie pattern can be extended with a count per node to support frequency-based autocomplete, and that a delete operation requires decrementing counts and pruning empty branches.
Visual Overview
Trie Pattern: Merchant Name Lookup
After inserting: RELIANCE, RELIABLE, HDFC
[root]
/ \
R H
| |
E D
| |
L F
| |
I C*
|
A
/ \
N B
| |
C L
| |
E* E*
* = isWord = true
Search "RELIANCE": R->E->L->I->A->N->C->E -> isWord=true -> TRUE
Search "RELI": R->E->L->I -> isWord=false -> FALSE
Prefix "RELI": R->E->L->I -> node exists -> TRUE
Autocomplete "RELI":
Walk to I node, DFS:
A -> N -> C -> E* (collect "RELIANCE")
A -> B -> L -> E* (collect "RELIABLE")
Result: ["RELIANCE", "RELIABLE"]
Key Takeaway
The Trie pattern uses a prefix tree to handle word insertion, exact-word lookup, and prefix matching, all in time proportional to the key length. Each edge carries one character, each root-to-node path spells a prefix, and words sharing a prefix share the same initial nodes. The isWord flag on each node distinguishes a complete word from a prefix that happens to pass through.
Insert walks character by character creating missing children and sets isWord on the last node. Search does the same walk and succeeds only when the path exists and isWord is true. StartsWith succeeds whenever the path exists, regardless of isWord. The shared traversal helper makes the code clean and the three operations differ by just one condition.
At the National Bank of India, Rajesh used the Trie pattern to power a merchant name lookup with autocomplete. A teller typing "RELI" instantly saw matching merchants, and exact lookups confirmed whether a name was registered. The trie handled 50,000 merchant names with prefix queries in microseconds.
The senior insight is knowing when to use the Trie pattern versus a HashMap. Tries win for prefix queries, autocomplete, and lexicographic iteration. HashMaps win for pure exact-match lookups with lower memory. In production, compressed tries (radix trees) merge single-child chains, and frequency counts per node enable ranked autocomplete.
Remember one sentence: The Trie pattern stores characters on edges, uses isWord to distinguish complete words from prefixes, and gives O(key length) operations for insert, search, and prefix matching.
---