Definition
- Trie – a tree where each edge represents one character, so every path from the root spells a prefix.
- End-of-word flag – a boolean on each node marking that the prefix spelled so far is a complete stored word.
- Insert – walk from root, create child nodes as needed with
computeIfAbsent, mark the final node. - Search – walk the path; return true only if the path exists and the final node's flag is set.
- startsWith – walk the path; return true if the path exists (flag ignored).
- Complexity – O(L) time per operation where L is the key length, independent of stored word count.
At the National Bank of India, the directory of IFSC branch codes is like a nested set of pigeonholes. Each digit typed at the counter picks the next drawer. A flag inside a drawer says whether a complete valid code ends there. Searching a code or checking whether any code begins with a few typed digits just means following the drawers.
Understanding the Concepts
What is a Trie?
A Trie (prefix tree) is a tree data structure where each edge represents one character. Every path from the root spells a prefix of a stored word. A boolean end-of-word flag on a node marks that the prefix up to that node is a complete word. This structure allows insert, exact search, and prefix search in time proportional to the key length.
package com.bank.service;
import java.util.HashMap;
import java.util.Map;
public class Trie {
private TrieNode root = new TrieNode();
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
}
node.isWord = true;
}
public boolean search(String word) {
TrieNode node = traverse(word);
return node != null && node.isWord;
}
public boolean startsWith(String prefix) {
return traverse(prefix) != null;
}
private TrieNode traverse(String key) {
TrieNode node = root;
for (char c : key.toCharArray()) {
node = node.children.get(c);
if (node == null) return null;
}
return node;
}
}
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isWord = false;
}
How does insert work?
Insert walks the word character by character from the root. At each character, it either follows an existing child or creates a new one using computeIfAbsent. After the last character, it sets the end-of-word flag to true.
package com.bank.service;
public class InsertDemo {
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("ICIC");
trie.insert("ICICI");
System.out.println(trie.search("ICIC")); // true
System.out.println(trie.search("ICICI")); // true
System.out.println(trie.search("ICI")); // false (prefix, not word)
System.out.println(trie.startsWith("ICI")); // true
}
}
true
true
false
true
How is search different from startsWith?
Both operations traverse the Trie identically. The only difference is the final check. Search requires the end-of-word flag to be true at the last node. startsWith only requires that the path exists, regardless of the flag. This is the key distinction interviewers look for.
// search: path must exist AND isWord must be true
public boolean search(String word) {
TrieNode node = traverse(word);
return node != null && node.isWord; // both conditions
}
// startsWith: path must exist (flag ignored)
public boolean startsWith(String prefix) {
return traverse(prefix) != null; // only path existence
}
What is the time and space complexity?
Each operation traverses at most L characters, where L is the key length. The time is independent of how many words are stored, which is the Trie's main advantage over hash-based lookups for prefix queries.
- Time – O(L) per operation where L is the key length.
- Space – O(total characters across all inserted words) in the worst case.
- Comparison – a HashSet gives O(L) search but cannot answer prefix queries without scanning all keys.
// Time per operation: O(L) where L = key length
// Independent of N (number of stored words)
// HashSet.contains("ICICI"): O(L) for hashing, but
// HashSet has no startsWith operation at all.
What is the HashMap vs fixed-array trade-off?
Using a HashMap for children handles any alphabet flexibly but has higher memory overhead and pointer chasing. A fixed array of 26 (for lowercase letters) is faster and more cache-friendly but wastes space when the alphabet is sparse.
| Aspect | HashMap Children | Fixed Array [26] |
|---|---|---|
| Alphabet | Any characters | Lowercase a-z only |
| Memory | Proportional to used children | 26 slots per node (wasteful if sparse) |
| Speed | Hash lookups, pointer chasing | Direct index, cache-friendly |
| Flexibility | High | Low |
// HashMap version
class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isWord;
}
// Fixed array version (lowercase only)
class TrieNodeArray {
TrieNodeArray[] children = new TrieNodeArray[26];
boolean isWord;
// Access: children[c - 'a']
}
What are the edge cases?
Edge cases include searching for an empty string, inserting the same word twice, and searching for a word that is a prefix of another stored word.
package com.bank.service;
public class TrieEdgeCases {
public static void main(String[] args) {
Trie trie = new Trie();
// Insert and search same word twice
trie.insert("HDFC");
trie.insert("HDFC");
System.out.println(trie.search("HDFC")); // true
// Word is prefix of another
trie.insert("HDFCBANK");
System.out.println(trie.search("HDFC")); // true (inserted separately)
System.out.println(trie.search("HDFCBANK")); // true
System.out.println(trie.startsWith("HDF")); // true
}
}
true
true
true
true
What are common mistakes?
The most common mistake is forgetting the end-of-word flag, causing search to return true for any prefix of a stored word. Another mistake is not returning false when a character is not found during traversal.
// WRONG: no isWord check in search
public boolean searchWrong(String word) {
TrieNode node = traverse(word);
return node != null; // returns true for prefixes too!
}
// CORRECT: check isWord
public boolean searchCorrect(String word) {
TrieNode node = traverse(word);
return node != null && node.isWord;
}
How would you apply this in a banking system?
At the National Bank of India, a Trie powers type-ahead for IFSC branch codes on the banking portal. Each keystroke calls startsWith to offer suggestions and search to determine whether the typed string is a complete valid code. Because the directory holds hundreds of thousands of codes, a per-keystroke cost proportional to the directory size would be unacceptable.
package com.bank.service;
import java.util.List;
import java.util.ArrayList;
public class IFSCTypeAheadService {
private final Trie trie = new Trie();
public void loadCodes(List<String> ifscCodes) {
for (String code : ifscCodes) trie.insert(code);
}
public boolean isValidCode(String code) {
return trie.search(code);
}
public boolean hasCodesStartingWith(String prefix) {
return trie.startsWith(prefix);
}
}
What should a senior engineer know?
A senior engineer should know that Tries are the basis for autocomplete, spell-check, IP routing (longest prefix match), and T9 predictive text. They should also know about compressed Tries (radix trees) that merge chains of single-child nodes to save space, and concurrent Tries for thread-safe lookups.
// Trie applications:
// 1. Autocomplete / type-ahead suggestions
// 2. Spell checking (edit-distance search)
// 3. IP routing (longest prefix match)
// 4. T9 predictive text input
// 5. Word games (Boggle, Scrabble)
// Compressed Trie (radix tree):
// Merges single-child chains: a->p->p->l->e becomes "apple" edge
// Saves space for sparse Tries
What are common interview follow-up questions?
Interviewers often ask follow-ups that build on the basic Trie:
- Add a delete operation that removes a word and cleans up orphan nodes.
- Add a method to list all words with a given prefix (DFS from the prefix node).
- Design a word search where dots match any character (wildcard search with backtracking).
// Follow-up: find all words with prefix
public List<String> findAllWithPrefix(String prefix) {
List<String> result = new ArrayList<>();
TrieNode node = traverse(prefix);
if (node != null) dfs(node, new StringBuilder(prefix), result);
return result;
}
private void dfs(TrieNode node, StringBuilder path, List<String> result) {
if (node.isWord) result.add(path.toString());
for (var entry : node.children.entrySet()) {
path.append(entry.getKey());
dfs(entry.getValue(), path, result);
path.deleteCharAt(path.length() - 1);
}
}
Visual Overview
Trie after inserting: "ICIC", "ICICI", "HDFC"
(root)
/ \
I H
| |
C D
| |
I F
| |
C* C*
|
I*
* = end-of-word flag set
search("ICIC"): I → C → I → C (isWord=true) → true
search("ICI"): I → C → I (isWord=false) → false
startsWith("ICI"): I → C → I (exists) → true
search("ICICI"): I → C → I → C → I (isWord=true) → true
search("ABC"): no 'A' child at root → false
Key Takeaway
A Trie is a prefix tree where each edge carries one character, so every path from the root spells a prefix. A boolean end-of-word flag tells me whether the prefix spelled up to that node is a complete stored word. The power of this structure is that insert, search, and startsWith all cost time proportional only to the key length, never to the number of stored words.
Insert walks from the root creating child nodes as needed and marks the last node. Search walks the same path and checks the end-of-word flag. startsWith is identical but ignores the flag. The subtle distinction between search (requires flag) and startsWith (ignores flag) is what interviewers listen for.
The design trade-off between a HashMap of children and a fixed array of 26 affects flexibility and performance. HashMap handles any alphabet; the fixed array is faster and cache-friendlier for lowercase-only inputs. A senior engineer also knows about compressed Tries and concurrent variants.
At the National Bank of India, I used a Trie for type-ahead on IFSC branch codes. Each keystroke called startsWith to decide whether to keep offering suggestions and search to check for a complete valid code. The directory held hundreds of thousands of codes, so per-keystroke cost had to be independent of the directory size.
Remember one sentence: a Trie walks one character per edge, search checks the end-of-word flag, and startsWith ignores it.
---