Implement a Trie for Autocomplete in Java
Problem
A trie (prefix tree) stores strings character by character along a path from the root, so all words sharing a prefix share the same branch.
Insert a list of words into a trie, then return every stored word that starts with a given prefix.
Java Program
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class TrieAutocomplete {
static class Node {
Map<Character, Node> children = new TreeMap<>(); // sorted, so suggestions come out alphabetically
boolean endOfWord;
}
private final Node root = new Node();
void insert(String word) {
Node node = root;
for (char c : word.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new Node()); // follow or create the branch
}
node.endOfWord = true;
}
List<String> suggest(String prefix) {
Node node = root;
for (char c : prefix.toCharArray()) {
node = node.children.get(c);
if (node == null) return new ArrayList<>(); // no word starts with this prefix
}
List<String> results = new ArrayList<>();
collect(node, new StringBuilder(prefix), results);
return results;
}
private void collect(Node node, StringBuilder path, List<String> out) {
if (node.endOfWord) out.add(path.toString());
for (Map.Entry<Character, Node> e : node.children.entrySet()) {
path.append(e.getKey());
collect(e.getValue(), path, out);
path.deleteCharAt(path.length() - 1); // backtrack
}
}
public static void main(String[] args) {
TrieAutocomplete trie = new TrieAutocomplete();
for (String w : new String[]{"car", "card", "care", "cart", "cat", "dog", "do"}) {
trie.insert(w);
}
System.out.println("car -> " + trie.suggest("car"));
System.out.println("ca -> " + trie.suggest("ca"));
System.out.println("do -> " + trie.suggest("do"));
System.out.println("x -> " + trie.suggest("x"));
}
}Output
Core Logic
Walking down the trie to the prefix's last node isolates exactly the words that start with it; a depth-first search below that node collects them.
- 1
insertfollows one child per character, creating missing nodes withcomputeIfAbsent, and marks the last node as the end of a word. - 2
suggestwalks the prefix; if any character is missing, no word starts with it and an empty list is returned. - 3
collectvisits every node below the prefix, adding the current path whenever it reaches an end-of-word node. - 4Children live in a
TreeMap, so the search visits them alphabetically and suggestions come out sorted.
do, the prefix node itself is a word end, so do is listed before dog.Key Point: Lookup cost depends on the prefix length, not on how many words are stored — which is why tries power autocomplete and spell checkers.
Why: Reaching the prefix takes L steps for a prefix of length L, then the search visits the k nodes beneath it; storage grows with the characters inserted, minus shared prefixes.
Key Concepts
Approach 2: Array Children with Prefix Counts
public class TrieArrayChildren {
static class Node {
Node[] next = new Node[26]; // one slot per lowercase letter
int wordsPassingThrough; // how many inserted words use this prefix
boolean endOfWord;
}
private final Node root = new Node();
void insert(String word) {
Node node = root;
for (char c : word.toCharArray()) {
int i = c - 'a';
if (node.next[i] == null) node.next[i] = new Node();
node = node.next[i];
node.wordsPassingThrough++;
}
node.endOfWord = true;
}
int countWithPrefix(String prefix) {
Node node = root;
for (char c : prefix.toCharArray()) {
node = node.next[c - 'a'];
if (node == null) return 0;
}
return node.wordsPassingThrough;
}
boolean contains(String word) {
Node node = root;
for (char c : word.toCharArray()) {
node = node.next[c - 'a'];
if (node == null) return false;
}
return node.endOfWord;
}
public static void main(String[] args) {
TrieArrayChildren trie = new TrieArrayChildren();
for (String w : new String[]{"car", "card", "care", "cart", "cat", "dog", "do"}) {
trie.insert(w);
}
System.out.println("Words starting with \"car\": " + trie.countWithPrefix("car"));
System.out.println("Words starting with \"d\": " + trie.countWithPrefix("d"));
System.out.println("contains(\"car\"): " + trie.contains("car"));
System.out.println("contains(\"ca\"): " + trie.contains("ca"));
}
}
Output
Core Logic
For lowercase words, an array of 26 children replaces the map, and a counter on each node answers "how many words start with this prefix?" instantly.
- 1
next[c - 'a']indexes a child directly, without hashing. - 2During
insert, every node on the path incrementswordsPassingThrough. - 3
countWithPrefixwalks the prefix and returns that node's counter. - 4
containsdistinguishes full words from mere prefixes usingendOfWord.
c-a-r path, and ca is a prefix but not a stored word, so contains("ca") is false.Key Point: Arrays make lookups faster but reserve 26 slots per node; the map version uses less memory when the alphabet is large or sparse.
Why: Each query walks one node per prefix character, while every node allocates a 26-slot array.
Key Concepts
Interview Questions
How is a trie different from a HashSet of words?
A HashSet checks whole words quickly but can't find every word with a given prefix without scanning all of them. A trie shares prefixes, so prefix queries are cheap.
How would you return only the top suggestions?
Store a popularity count on word-ending nodes and keep the best k results in a small heap while collecting, instead of returning every match.