Autocoder

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 operationO(L) for a word of length L
MemoryUp to alphabet size times total characters
Signal wordsprefix, autocomplete, dictionary, wildcard, XOR
LanguagesPython 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

Trie (Prefix Tree) Interview Questions: questions with worked answers

  1. 1

    Implement a trie with insert, search and startsWith

    easy

    Each 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.

    python
    class 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 None
    java
    class 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. 2

    Longest common prefix of an array of strings

    easy

    Insert 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.

    python
    def 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)
    java
    String 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. 3

    Count words equal to and starting with a prefix

    medium

    Store 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.

    python
    class 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 0
    java
    class 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. 4

    Add and search words with the wildcard dot

    medium

    Insert 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).

    python
    class 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)
    java
    class 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. 5

    Replace words with their shortest dictionary root

    medium

    Build 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).

    python
    def 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())
    java
    String 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. 6

    Longest word that can be built one letter at a time

    medium

    Insert 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.

    python
    def 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 best
    java
    String 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. 7

    Autocomplete: top three suggestions for each typed prefix

    medium

    Store 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.

    python
    import 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 out
    java
    List<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. 8

    Count distinct substrings of a string

    medium

    Every 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.

    python
    def 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 count
    java
    int 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. 9

    Word Search II: find all dictionary words in a grid

    hard

    Running 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.

    python
    def 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 res
    java
    class 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. 10

    Maximum XOR of two numbers in an array

    hard

    Treat 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).

    python
    def 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 best
    java
    int 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

See all in this section