Basic Trie

Autocomplete

Navigate to the node representing the prefix, then DFS from there to collect all words in the subtree. Each path to an 'end of word' node gives one suggestion. Can limit results or rank by frequency.

O(m + k)

O(k)

How It Works

Autocomplete combines the two trie primitives: first navigate from the root to the node representing the typed prefix in O(P) steps, then run a DFS through that node's subtree, appending characters to a running path and emitting a suggestion whenever an end-of-word node is reached. Every word below the prefix node shares the prefix by construction, so no filtering is needed.

The DFS costs time proportional to the subtree size, which for large dictionaries motivates two standard optimizations: cap the number of results and prune the DFS once the cap is hit (visiting children in alphabetical order yields lexicographically smallest suggestions first), or precompute the top-k completions at each node during insertion so queries become O(P + k) lookups. This prefix-scoped enumeration is exactly what hash-based structures cannot provide without scanning every stored key.

Step-by-Step Visualization

Autocomplete prefix 'app': find all words starting with it

Navigateroot → a → p → p

1/2

Code

Java

static List<String> autocomplete(Trie trie, String prefix) {
  TrieNode node = trie.root;
  for (char ch : prefix.toCharArray()) {
    if (!node.children.containsKey(ch)) return new ArrayList<>();
    node = node.children.get(ch);
  }

  List<String> results = new ArrayList<>();
  dfs(node, new StringBuilder(prefix), results);
  return results;
}

static void dfs(TrieNode node, StringBuilder path, List<String> results) {
  if (node.isEnd) results.add(path.toString());
  for (Map.Entry<Character, TrieNode> e : node.children.entrySet()) {
    path.append(e.getKey());
    dfs(e.getValue(), path, results);
    path.deleteCharAt(path.length() - 1);
  }
}

Tips & Gotchas

1Navigate to prefix node, then DFS to collect all words

2k = number of words with that prefix

3Can limit results with early termination

Practice Problems

1Search Suggestions System
2Design Search Autocomplete System
3Top K Frequent Words

About the Basic Trie Pattern

Each node has up to 26 children (for lowercase letters). Insert by walking/creating nodes for each character. Search by walking the tree — if you can follow the entire word and the last node is marked as 'end', the word exists.

Key insight

Use a trie when you need prefix-based operations that hash maps can't do efficiently — like 'find all words starting with X' or 'find word matching pattern with wildcards'.

Common Trie Interview Problems

Implement Trie
Word Search II
Design Add and Search Words
Replace Words
Maximum XOR of Two Numbers

Frequently Asked Questions

How do I return suggestions in alphabetical order without sorting afterwards?

Visit children in character order during the DFS — index 0 through 25 for a lowercase array — and emit words as end nodes are found. The traversal order then matches lexicographic order natively, so the first k words collected are already the k smallest and the search can stop early.

How is ranking by popularity handled, as in a real search box?

Store a frequency or hotness score on each end node, then either collect all subtree words and pick the top k with a small heap, or precompute a cached top-k list per node updated on insertion. The cache trades extra memory and insert work for O(P + k) query time, which is the right trade for read-heavy systems.