Trie Visualization for Coding Interviews
Prefix tree: insert words, search, prefix lookup.
Concept
A trie, or prefix tree, is a rooted tree where every edge is labeled with a single character and every path from the root to a marked node spells out a stored string. The structure makes three operations extremely cheap: inserting a word in O(L), checking if a word is present in O(L), and asking whether any stored word starts with a given prefix in O(L), where L is the length of the query, independent of how many words are in the trie. That prefix-in-query-length property is why tries underlie autocomplete, spell-checkers, IP routing tables, dictionary compression, and the Aho-Corasick multi-pattern matcher. The trade-off is memory: a naive trie with a 26-way children array per node spends a lot of space on sparse letters. Production code uses HashMaps, sorted arrays, or compressed ternary or radix variants to cut the overhead. The basic insight is unchanged: branch on the next character and you can walk character-by-character through every prefix relationship in the set.
How it works
Every node stores a mapping from character to child node and a boolean flag indicating whether a word ends at this node. Insert walks the tree from the root, following or creating child edges for each character of the input word, and marks the terminal node as end-of-word. Contains walks the same path but returns true only if the final node exists AND its end-of-word flag is set; a prefix match without terminal flag means the query is a prefix of some stored word but is not itself stored. StartsWith is even simpler: walk as far as the prefix extends and return true if every character was found, regardless of the terminal flag. Delete requires more care and usually runs as a recursive post-order: if the current node's children map is empty after the descendant delete and this node is not itself a word end, the node can be removed from its parent. Variations abound. A compressed trie (radix tree) collapses chains of single-child nodes into edges labeled with substrings, trading fixed O(L) per operation for much lower memory on sparse data. A ternary search trie replaces the wide children array with a small BST per node, which is slower per step but extremely compact.
Implementation
import java.util.HashMap;
import java.util.Map;
public class Trie {
static class TrieNode {
final Map<Character, TrieNode> children = new HashMap<>();
boolean endOfWord;
}
private final TrieNode root = new TrieNode();
/** Insert word into the trie. */
public void insert(String word) {
if (word == null) throw new IllegalArgumentException("word cannot be null");
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
node = node.children.computeIfAbsent(c, k -> new TrieNode());
}
node.endOfWord = true;
}
/** True iff word is stored as a complete word. */
public boolean contains(String word) {
TrieNode node = walk(word);
return node != null && node.endOfWord;
}
/** True iff any stored word begins with the given prefix. */
public boolean startsWith(String prefix) {
return walk(prefix) != null;
}
private TrieNode walk(String s) {
TrieNode node = root;
for (int i = 0; i < s.length(); i++) {
node = node.children.get(s.charAt(i));
if (node == null) return null;
}
return node;
}
/** Remove word if present. Returns true if a word was actually removed. */
public boolean delete(String word) {
return delete(root, word, 0);
}
private boolean delete(TrieNode node, String word, int depth) {
if (depth == word.length()) {
if (!node.endOfWord) return false;
node.endOfWord = false;
return node.children.isEmpty();
}
char c = word.charAt(depth);
TrieNode child = node.children.get(c);
if (child == null) return false;
boolean shouldPrune = delete(child, word, depth + 1);
if (shouldPrune) {
node.children.remove(c);
return !node.endOfWord && node.children.isEmpty();
}
return false;
}
}Complexity
- Insert:
O(L) - Contains:
O(L) - StartsWith:
O(L) - Space:
O(total characters across all words)
Common pitfalls
- Treating the presence of a node as proof that the word is stored - you must also check the endOfWord flag.
- Using a fixed 26-slot array for children and then feeding the trie Unicode input or mixed case.
- Forgetting to prune empty branches on delete, leaving a ghost trie that grows monotonically.
- Copy-pasting startsWith as contains or vice versa - they differ only in the final flag check and the bug is silent.
- Recursing into children without guarding for null at the root when the trie is empty.
Key design decisions & trade-offs
- Children representation — Chosen: HashMap of character to node. Handles arbitrary alphabets and is memory-efficient for sparse inputs; costs a hash per step versus an array index.
- Trie vs hash set — Chosen: Trie when prefix queries matter. Hash sets are faster for exact membership but cannot answer 'any word with prefix p' without scanning every key.
- Plain trie vs radix tree — Chosen: Plain trie for clarity, radix for memory. Radix trees collapse single-child chains and drastically cut memory for sparse sets, at the cost of more complex splits on insert.
Practice problems
Interview follow-ups
- Extend the trie to support wildcard (.) queries with backtracking.
- Implement autocomplete: return the top-k words with a given prefix using DFS and a heap of frequencies.
- Compress chains of single-child nodes into a radix tree.
- Use a trie as the state machine for the Aho-Corasick multi-pattern matcher.
- Serialize and deserialize the trie for fast cold-start loading.
Why it matters
Trie is a core part of the Trees toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".