Building a Trie from Scratch
Construct a prefix tree that supports insert and search in O(L), and learn how to extend it for autocomplete prompts.
Problem Statement
Design a trie that inserts and queries words by prefix in linear time relative to the word length.
Why This Problem Matters
- Tries appear as follow-ups to hash map problems when prefix queries are required.
- They test whether you can trade memory for speed and reason using the word length L.
- Understanding tries prepares you for autocomplete, word search, and DNA pattern questions.
Thought Process
Model the node structure
Decide between an array of fixed children or a map keyed by character. Highlight the trade-off between memory usage and flexibility.
Track word termination explicitly
Use an isWord flag so the trie can differentiate between a prefix and a completed word. Without it, search would return true too early.
Explain runtime using word length
Operations depend on L, not the number of stored words. That is the key selling point over hash maps for prefix queries.
Step-by-Step Reasoning
- Define a Node class with child references and a boolean isWord flag.
- During insert, traverse or create nodes for each character, marking the final node as a word.
- For search, reuse the traversal and ensure the final node has isWord = true.
- For startsWith, reuse traversal and simply check that traversal did not return null.
Dry Run
Insert "cat" and "car"
Nodes c → a → t and c → a → r share the prefix, demonstrating memory sharing.
startsWith("ca")
Traversal stops at node for a, which exists, so the prefix is valid.
Complexity Analysis
Time
O(L)
Space
O(AL)
Why
Operations touch each character once. Space depends on alphabet size A and the number of stored characters across words.
Annotated Solution
import java.util.HashMap;
import java.util.Map;
public class Trie {
private static class Node {
Map<Character, Node> children = new HashMap<>();
boolean isWord = false;
}
private final Node root = new Node();
public void insert(String word) {
Node current = root;
for (char c : word.toCharArray()) {
current = current.children.computeIfAbsent(c, key -> new Node());
}
current.isWord = true;
}
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 seq) {
Node current = root;
for (char c : seq.toCharArray()) {
current = current.children.get(c);
if (current == null) {
return null;
}
}
return current;
}
}Each insertion or lookup only touches nodes along the word path, so the runtime depends on the word length L rather than the number of stored words.
Common Pitfalls
- Neglecting to mark the terminal node causes search("word") to return false even after insertion.
- Using a fixed-size array without considering uppercase or special characters can lead to index errors.
Follow-Up Questions
- How would you support deleting a word while keeping the structure compact?
- What changes if the alphabet is the full Unicode set? Discuss sparse child maps or radix trees.