Trie (Prefix Tree) Interview Questions
Last updated 2026-11-19
A trie, or prefix tree, stores strings character by character so that every word sharing a prefix shares a path. That makes prefix lookups cost O(L), independent of how many words are stored, which is exactly what autocomplete, spell checkers and many string puzzles need.
This page covers trie problems from the basic implementation to Word Search II and the binary-trie maximum XOR trick. Every problem gives the idea, Python and Java code, complexity and edge cases. If you are short on string basics first read string interview questions.
| Cost per operation | O(L) for a word of length L |
|---|---|
| Memory | Up to alphabet size times total characters |
| Signal words | prefix, autocomplete, dictionary, wildcard, XOR |
| Languages | Python and Java |
The pattern and when to spot it
Reach for a trie when many words share prefixes and you are asked about prefixes: count words with a prefix, find the shortest root of a word, autocomplete or check whether a path in a grid spells a dictionary word. A hash set answers exact membership well but cannot enumerate or prune by prefix.
A trie also works over bits. Insert numbers as fixed-length binary strings and you can greedily pick the opposite bit at each level, the standard way to maximise an XOR. In grid word problems the trie lets one DFS search for all words at once and stop a branch as soon as the prefix is not in the dictionary.
Implementation choices
- Dictionary children are shorter to write in Python and handle any alphabet. Fixed arrays of 26 are faster in Java but waste memory for sparse tries.
- Store the full word at the end node when you need to return it, instead of rebuilding it from the path.
- Use an end-of-word marker. Without it you cannot tell apart a stored word from a mere prefix.
- For huge dictionaries consider a compressed (radix) trie, and mention it as a follow-up.
Trie (Prefix Tree) Interview Questions: questions with worked answers
1 Implement a trie with insert, search and startsWith
easyEach node holds a map from character to child plus an end-of-word flag. Insert walks and creates missing nodes. Search must end on a node with the flag set, while startsWith only needs the path to exist. Using one helper that returns the final node keeps both methods short. Time O(L) per operation for word length L, space O(total characters) overall. Edge cases: empty string, a word that is a prefix of another (flag needed), searching a prefix that is not a stored word.
pythonclass Trie: def __init__(self): self.root = {} def insert(self, w): n = self.root for ch in w: n = n.setdefault(ch, {}) n['$'] = True def _find(self, s): n = self.root for ch in s: if ch not in n: return None n = n[ch] return n def search(self, w): n = self._find(w) return n is not None and '$' in n def starts_with(self, p): return self._find(p) is not Nonejavaclass Trie { private static class Node { Node[] next = new Node[26]; boolean end; } private final Node root = new Node(); void insert(String w) { Node n = root; for (char c : w.toCharArray()) { if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node(); n = n.next[c - 'a']; } n.end = true; } private Node find(String s) { Node n = root; for (char c : s.toCharArray()) { n = n.next[c - 'a']; if (n == null) return null; } return n; } boolean search(String w) { Node n = find(w); return n != null && n.end; } boolean startsWith(String p) { return find(p) != null; } }2 Longest common prefix of an array of strings
easyInsert all strings and walk from the root while the current node has exactly one child and is not the end of a word. The path length is the prefix. For this question sorting and comparing the first and last strings is also O(total length). Time O(total characters), space O(total characters). Edge cases: an empty string in the array (prefix is empty), a single string (prefix is the string), no shared first letter.
pythondef longest_common_prefix(words): root = {} for w in words: n = root for ch in w: n = n.setdefault(ch, {}) n['$'] = True out, n = [], root while len(n) == 1 and '$' not in n: ch = next(iter(n)) out.append(ch) n = n[ch] return ''.join(out)javaString longestCommonPrefix(String[] words) { String first = words[0]; int end = first.length(); for (String w : words) { int i = 0; while (i < end && i < w.length() && w.charAt(i) == first.charAt(i)) i++; end = i; } return first.substring(0, end); }3 Count words equal to and starting with a prefix
mediumStore two counters on each node: how many words pass through it, and how many end at it. Insert increments the pass count along the path and the end count at the last node. Queries read one counter at the final node. Supporting erase just decrements. Time O(L) per operation, space O(total characters). Edge cases: prefix not present returns 0, duplicate words increase the counters, erasing a word that was never inserted should be guarded.
pythonclass CountTrie: def __init__(self): self.ch, self.pas, self.end = {}, 0, 0 def insert(self, w): n = self for c in w: n = n.ch.setdefault(c, CountTrie()) n.pas += 1 n.end += 1 def _walk(self, s): n = self for c in s: if c not in n.ch: return None n = n.ch[c] return n def count_equal(self, w): n = self._walk(w) return n.end if n else 0 def count_prefix(self, p): n = self._walk(p) return n.pas if n else 0javaclass CountTrie { private final CountTrie[] ch = new CountTrie[26]; private int pass, end; void insert(String w) { CountTrie n = this; for (char c : w.toCharArray()) { if (n.ch[c - 'a'] == null) n.ch[c - 'a'] = new CountTrie(); n = n.ch[c - 'a']; n.pass++; } n.end++; } private CountTrie walk(String s) { CountTrie n = this; for (char c : s.toCharArray()) { n = n.ch[c - 'a']; if (n == null) return null; } return n; } int countEqual(String w) { CountTrie n = walk(w); return n == null ? 0 : n.end; } int countPrefix(String p) { CountTrie n = walk(p); return n == null ? 0 : n.pass; } }4 Add and search words with the wildcard dot
mediumInsert normally. When searching, a letter follows one child, but a dot must try every child, so use DFS. The dot makes the worst case exponential in the number of dots only for pathological tries; in practice it is bounded by the trie size. Time O(L) without dots, O(26^d * L) worst case with d dots, bounded by trie size, space O(total characters). Edge cases: all dots, pattern longer than any word, a pattern that matches only a prefix of a stored word (must check the end flag).
pythonclass WordDictionary: def __init__(self): self.root = {} def add_word(self, w): n = self.root for c in w: n = n.setdefault(c, {}) n['$'] = True def search(self, w): def dfs(i, n): if i == len(w): return '$' in n c = w[i] if c == '.': return any(dfs(i + 1, v) for k, v in n.items() if k != '$') return c in n and dfs(i + 1, n[c]) return dfs(0, self.root)javaclass WordDictionary { private static class Node { Node[] next = new Node[26]; boolean end; } private final Node root = new Node(); void addWord(String w) { Node n = root; for (char c : w.toCharArray()) { if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node(); n = n.next[c - 'a']; } n.end = true; } boolean search(String w) { return dfs(w, 0, root); } private boolean dfs(String w, int i, Node n) { if (n == null) return false; if (i == w.length()) return n.end; char c = w.charAt(i); if (c != '.') return dfs(w, i + 1, n.next[c - 'a']); for (Node child : n.next) if (dfs(w, i + 1, child)) return true; return false; } }5 Replace words with their shortest dictionary root
mediumBuild a trie of the roots. For each word in the sentence walk the trie and stop at the first node marked as a word end; that prefix is the replacement. If the walk fails before any end, keep the original word. Time O(total dictionary length + sentence length), space O(dictionary length). Edge cases: a word that has no root, a root equal to the whole word, several roots sharing a prefix (shortest wins).
pythondef replace_words(roots, sentence): trie = {} for r in roots: n = trie for c in r: n = n.setdefault(c, {}) n['$'] = True def shortest(w): n = trie for i, c in enumerate(w): if c not in n: break n = n[c] if '$' in n: return w[:i + 1] return w return ' '.join(shortest(w) for w in sentence.split())javaString replaceWords(List<String> roots, String sentence) { Set<String> set = new HashSet<>(roots); StringBuilder sb = new StringBuilder(); for (String w : sentence.split(" ")) { String rep = w; for (int i = 1; i <= w.length(); i++) { if (set.contains(w.substring(0, i))) { rep = w.substring(0, i); break; } } if (sb.length() > 0) sb.append(' '); sb.append(rep); } return sb.toString(); }6 Longest word that can be built one letter at a time
mediumInsert all words, then DFS from the root, moving only into children that mark the end of a word. The deepest reachable node is the answer; break ties by lexicographic order by visiting children in alphabetical order and replacing only on strictly longer. Time O(total characters), space O(total characters). Edge cases: no word of length 1 (answer empty), ties on length, duplicate words.
pythondef longest_word(words): root = {} for w in words: n = root for c in w: n = n.setdefault(c, {}) n['$'] = w best = '' stack = [root] while stack: n = stack.pop() for c, v in n.items(): if c == '$': continue if '$' in v: w = v['$'] if len(w) > len(best) or (len(w) == len(best) and w < best): best = w stack.append(v) return bestjavaString longestWord(String[] words) { Set<String> set = new HashSet<>(Arrays.asList(words)); String best = ""; for (String w : words) { boolean ok = true; for (int i = 1; i < w.length() && ok; i++) ok = set.contains(w.substring(0, i)); if (ok && (w.length() > best.length() || (w.length() == best.length() && w.compareTo(best) < 0))) best = w; } return best; }7 Autocomplete: top three suggestions for each typed prefix
mediumStore sorted words and, for each prefix typed so far, binary search the first word at or after the prefix and check the next three. That is a trie-free way to get the same result; a trie that keeps the three best words at each node answers each keystroke in O(L). Time O(n log n) to sort, O(L log n) per keystroke, space O(n). Edge cases: no matches (empty list), fewer than three matches, repeated products.
pythonimport bisect def suggest(products, typed): products.sort() out, prefix = [], '' for c in typed: prefix += c i = bisect.bisect_left(products, prefix) out.append([p for p in products[i:i + 3] if p.startswith(prefix)]) return outjavaList<List<String>> suggest(String[] products, String typed) { Arrays.sort(products); List<List<String>> out = new ArrayList<>(); String prefix = ""; for (char c : typed.toCharArray()) { prefix += c; int lo = 0, hi = products.length; while (lo < hi) { int mid = (lo + hi) / 2; if (products[mid].compareTo(prefix) < 0) lo = mid + 1; else hi = mid; } List<String> cur = new ArrayList<>(); for (int i = lo; i < Math.min(lo + 3, products.length); i++) if (products[i].startsWith(prefix)) cur.add(products[i]); out.add(cur); } return out; }8 Count distinct substrings of a string
mediumEvery substring is a prefix of some suffix. Insert every suffix into a trie and count the nodes created; each new node is one new distinct substring. This is simple but quadratic, so mention suffix arrays or automata for large inputs. Time O(n^2), space O(n^2). Edge cases: empty string gives 0, a string of one repeated letter has n distinct substrings, case sensitivity.
pythondef count_distinct(s): root, count = {}, 0 for i in range(len(s)): n = root for c in s[i:]: if c not in n: n[c] = {} count += 1 n = n[c] return countjavaint countDistinct(String s) { int[][] t = new int[s.length() * (s.length() + 1) / 2 + 1][26]; int nodes = 1, count = 0; for (int i = 0; i < s.length(); i++) { int n = 0; for (int j = i; j < s.length(); j++) { int c = s.charAt(j) - 'a'; if (t[n][c] == 0) { t[n][c] = nodes++; count++; } n = t[n][c]; } } return count; }9 Word Search II: find all dictionary words in a grid
hardRunning a separate DFS per word is far too slow. Build a trie of all words, then DFS from every cell, following only letters that exist in the trie. When a node holds a full word, record it and clear it so it is not reported twice. Pruning exhausted trie branches speeds the search up further. Time O(R * C * 4 * 3^(L-1)) worst case, much faster with pruning, space O(total dictionary characters + L). Edge cases: a cell reused within one path (mark visited and restore), the same word reachable several ways (report once), empty board.
pythondef find_words(board, words): root = {} for w in words: n = root for c in w: n = n.setdefault(c, {}) n['$'] = w R, C, res = len(board), len(board[0]), [] def dfs(r, c, n): ch = board[r][c] nxt = n.get(ch) if not nxt: return if '$' in nxt: res.append(nxt.pop('$')) board[r][c] = '#' for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < R and 0 <= nc < C and board[nr][nc] != '#': dfs(nr, nc, nxt) board[r][c] = ch if not nxt: n.pop(ch) for r in range(R): for c in range(C): dfs(r, c, root) return resjavaclass Node { Node[] next = new Node[26]; String word; } List<String> findWords(char[][] b, String[] words) { Node root = new Node(); for (String w : words) { Node n = root; for (char c : w.toCharArray()) { if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node(); n = n.next[c - 'a']; } n.word = w; } List<String> res = new ArrayList<>(); for (int r = 0; r < b.length; r++) for (int c = 0; c < b[0].length; c++) dfs(b, r, c, root, res); return res; } private void dfs(char[][] b, int r, int c, Node p, List<String> res) { char ch = b[r][c]; if (ch == '#' || p.next[ch - 'a'] == null) return; Node n = p.next[ch - 'a']; if (n.word != null) { res.add(n.word); n.word = null; } b[r][c] = '#'; if (r > 0) dfs(b, r - 1, c, n, res); if (c > 0) dfs(b, r, c - 1, n, res); if (r < b.length - 1) dfs(b, r + 1, c, n, res); if (c < b[0].length - 1) dfs(b, r, c + 1, n, res); b[r][c] = ch; }10 Maximum XOR of two numbers in an array
hardTreat each number as a 31-bit binary string and insert it into a binary trie, most significant bit first. For each number walk the trie choosing, at every bit, the child with the opposite bit when it exists, since that sets this bit of the XOR to 1. Track the best result. Time O(31 * n), space O(31 * n). Edge cases: single element (XOR with itself is 0), all numbers equal, zeros, non-negative inputs assumed (negative numbers need a sign-bit rule).
pythondef max_xor(nums): root = {} for x in nums: n = root for i in range(30, -1, -1): n = n.setdefault((x >> i) & 1, {}) best = 0 for x in nums: n, cur = root, 0 for i in range(30, -1, -1): b = (x >> i) & 1 if (1 - b) in n: cur |= 1 << i n = n[1 - b] else: n = n[b] best = max(best, cur) return bestjavaint maxXor(int[] nums) { int[][] t = new int[nums.length * 31 + 1][2]; int cnt = 1; for (int x : nums) { int n = 0; for (int i = 30; i >= 0; i--) { int b = (x >> i) & 1; if (t[n][b] == 0) t[n][b] = cnt++; n = t[n][b]; } } int best = 0; for (int x : nums) { int n = 0, cur = 0; for (int i = 30; i >= 0; i--) { int b = (x >> i) & 1; if (t[n][1 - b] != 0) { cur |= 1 << i; n = t[n][1 - b]; } else n = t[n][b]; } best = Math.max(best, cur); } return best; }
Frequently asked questions
When is a trie better than a hash map of words?
A trie is better when you need prefix operations such as autocomplete, counting words with a prefix or pruning a search. A hash map is simpler and faster for plain exact-match lookups.
What is the space complexity of a trie?
In the worst case it is O(total characters across all words) nodes, each holding up to alphabet-size child pointers, so a 26-letter array per node can be wasteful for sparse data.
How do I delete a word from a trie?
Walk to the end node and clear its flag or decrement a counter. Then, going back up, remove nodes that have no children and are not the end of another word.
Do trie problems appear in coding rounds?
They are less frequent than arrays or trees but appear in product company tests, usually as implement-a-trie or Word Search II. The DSA coding round guide lists topics to prioritise.
Related guides
More in DSA Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions
- Array interview questions with worked solutions
- Backtracking interview questions with worked solutions
- BFS (Breadth-First Search) Interview Questions
- Binary search interview questions with worked solutions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions