Trie Questions 2026: 12+ Problems [Solved]

Last Updated: June 2026

Why Trie is a High-Signal Interview Topic

Candidates report Trie problems in roughly 8-12% of FAANG rounds, particularly at companies with search products (Google, Amazon, Microsoft). Based on public preparation resources and candidate-reported interview threads, Trie questions signal understanding of string optimization beyond hash maps.

The signature of a Trie problem: the problem involves prefixes, dictionary lookup with wildcards, or retrieving all strings matching a pattern. If you reach for a HashMap and it gives O(L * N) per prefix query, a Trie cuts it to O(L).

Trie Node and Implementation

class TrieNode:
    def __init__(self):
        self.children = {}         # char -> TrieNode
        self.is_end = False        # marks end of a valid word


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """
        Insert word into Trie.
        Time: O(L) where L = word length  Space: O(L) new nodes
        """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        """
        Returns True if word exists in Trie.
        Time: O(L)  Space: O(1)
        """
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        """
        Returns True if any word starts with prefix.
        Time: O(L)  Space: O(1)
        """
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Array-based Trie (faster, fixed alphabet):

class TrieNodeArray:
    def __init__(self):
        self.children = [None] * 26   # fixed alphabet a-z
        self.is_end = False

    def get_child(self, c):
        return self.children[ord(c) - ord('a')]

    def set_child(self, c, node):
        self.children[ord(c) - ord('a')] = node

Array-based is faster in practice (index vs hash lookup) but less flexible.

Practice Questions with Solutions

Problem 1: Implement Trie (Prefix Tree) (MEDIUM)

Asked at: Amazon, Google, Microsoft, Adobe - the standard Trie implementation problem

The Trie class shown above is the complete solution. Key methods: insert, search, startsWith.

# Example
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))    # True
print(trie.search("app"))      # False (not inserted, only apple)
print(trie.starts_with("app")) # True
trie.insert("app")
print(trie.search("app"))      # True

Complexity: Insert/Search/StartsWith all O(L), Space O(SIGMA * L * N)

Problem 2: Search a Word - Design Add and Search (MEDIUM)

Asked at: Amazon, Google, Facebook - Trie with wildcard '.'

class WordDictionary:
    """
    Supports adding words and searching with '.' wildcard.
    '.' matches any single character.
    """
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        """
        Time: O(26^(number of dots) * L) worst case
        """
        def dfs(node, idx):
            if idx == len(word):
                return node.is_end

            char = word[idx]
            if char == '.':
                for child in node.children.values():
                    if dfs(child, idx + 1):
                        return True
                return False
            else:
                if char not in node.children:
                    return False
                return dfs(node.children[char], idx + 1)

        return dfs(self.root, 0)

# Example
wd = WordDictionary()
wd.add_word("bad"); wd.add_word("dad"); wd.add_word("mad")
print(wd.search("pad"))   # False
print(wd.search("bad"))   # True
print(wd.search(".ad"))   # True
print(wd.search("b.."))   # True

Problem 3: Word Search II (HARD)

Asked at: Amazon, Google, Microsoft, Facebook - backtracking + Trie

Problem: Given m x n board and list of words, return all words found on the board (can use adjacent cells, not revisiting).

def find_words(board, words):
    """
    Build Trie of all words. DFS from every cell.
    Prune: if current path is not a prefix in Trie, stop.
    Time: O(M * N * 4^L * W) -> optimized to O(M * N * 4^L) with Trie pruning
    """
    trie = TrieNode()

    # Build Trie
    for word in words:
        node = trie
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = word  # store word at end node

    rows, cols = len(board), len(board[0])
    result = []

    def dfs(r, c, node):
        char = board[r][c]
        if char not in node.children:
            return

        next_node = node.children[char]

        if next_node.is_end:
            result.append(next_node.is_end)
            next_node.is_end = False  # avoid duplicates

        board[r][c] = '#'  # mark visited

        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                dfs(nr, nc, next_node)

        board[r][c] = char  # restore

        # Prune: if node has no children and no word, remove it
        if not next_node.children and not next_node.is_end:
            del node.children[char]

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, trie)

    return result

# Example
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
words = ["oath","pea","eat","rain"]
print(find_words(board, words))  # ["eat","oath"]

Complexity: Time O(M * N * 4^L) with pruning, Space O(SIGMA * L * N)

Problem 4: Replace Words (MEDIUM)

Asked at: Google, Amazon

Problem: Given a dictionary of root words and a sentence, replace each word in the sentence with its shortest root in the dictionary (or keep as is if no root found).

def replace_words(dictionary, sentence):
    """
    Build Trie of roots. For each word in sentence, find shortest matching prefix.
    Time: O(total_chars)  Space: O(total_dict_chars)
    """
    trie = Trie()
    for root in dictionary:
        trie.insert(root)

    def find_root(word):
        node = trie.root
        for i, char in enumerate(word):
            if char not in node.children:
                return word
            node = node.children[char]
            if node.is_end:
                return word[:i + 1]
        return word

    return ' '.join(find_root(word) for word in sentence.split())

# Example
print(replace_words(["cat","bat","rat"], "the cattle was rattled by the battery"))
# "the cat was rat by the bat"

Complexity: Time O(total_chars), Space O(total_dict_chars)

Problem 5: Autocomplete System (HARD)

Asked at: Google, Amazon, Microsoft - design question

class AutocompleteSystem:
    """
    Stores sentences with frequencies. Given prefix, return top 3 by frequency.
    """
    def __init__(self, sentences, times):
        self.root = TrieNode()
        self.current = ""

        # TrieNode also stores {sentence: count}
        for node in self._all_nodes():
            node.counts = {}

        for sentence, time in zip(sentences, times):
            self._insert(sentence, time)

    def _all_nodes(self):
        yield self.root

    def _insert(self, sentence, count):
        node = self.root
        for char in sentence:
            if char not in node.children:
                node.children[char] = TrieNode()
                node.children[char].counts = {}
            node = node.children[char]
            node.counts[sentence] = node.counts.get(sentence, 0) + count
        node.is_end = True

    def input(self, c):
        if c == '#':
            self._insert(self.current, 1)
            self.current = ""
            return []

        self.current += c
        node = self.root
        for char in self.current:
            if char not in node.children:
                return []
            node = node.children[char]

        # Return top 3 by count, then lexicographic
        counts = node.counts
        top3 = sorted(counts.keys(), key=lambda x: (-counts[x], x))[:3]
        return top3

Problem 6: Concatenated Words (HARD)

Asked at: Amazon, Google

def find_all_concatenated_words(words):
    """
    Build Trie of all words.
    For each word, check if it can be split into 2+ words from dictionary.
    Use DFS on the Trie.
    Time: O(N * L^2)  Space: O(N * L)
    """
    word_set = set(words)

    def can_form(word, count):
        if not word and count >= 2:
            return True
        if not word:
            return False

        for i in range(1, len(word) + 1):
            prefix = word[:i]
            if prefix in word_set:
                if can_form(word[i:], count + 1):
                    return True
        return False

    return [word for word in words if can_form(word, 0)]

# Example
print(find_all_concatenated_words(["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]))
# ["catsdogcats","dogcatsdog","ratcatdogcat"]

Problem 7: Maximum XOR of Two Numbers (HARD)

Asked at: Google, Amazon - the canonical bitwise Trie problem

Problem: Given an array of integers, find the maximum XOR of any two numbers.

def find_maximum_xor(nums):
    """
    Build a bitwise Trie over the 32-bit representation of each number.
    For each number, greedily walk the Trie choosing the OPPOSITE bit
    at each level to maximize XOR.
    Time: O(32 * n)  Space: O(32 * n)
    """
    root = {}
    HIGH = 31

    # Insert each number bit by bit (most significant first)
    for num in nums:
        node = root
        for i in range(HIGH, -1, -1):
            bit = (num >> i) & 1
            node = node.setdefault(bit, {})

    best = 0
    for num in nums:
        node = root
        cur = 0
        for i in range(HIGH, -1, -1):
            bit = (num >> i) & 1
            want = 1 - bit            # opposite bit maximizes this position
            if want in node:
                cur |= (1 << i)       # this bit contributes to XOR
                node = node[want]
            else:
                node = node[bit]
        best = max(best, cur)
    return best

# Example
print(find_maximum_xor([3, 10, 5, 25, 2, 8]))   # 28 (5 XOR 25)

Dry run on the high bits of 5 (00101) and 25 (11001): at the top bit, 25 has a 1; walking the Trie from 5 we greedily pick the opposite bit (1) where available, accumulating XOR positions. The greedy choice is optimal because a higher bit dominates all lower bits combined.

Complexity: Time O(32 * n), Space O(32 * n)

Problem 8: Longest Word in Dictionary (MEDIUM)

Asked at: Amazon, Google

Problem: Find the longest word that can be built one character at a time by other words in the list. Tie broken by lexicographically smallest.

def longest_word(words):
    """
    Insert all words. A word is buildable only if every prefix
    (of length 1..len) is also a complete word in the Trie.
    Time: O(total_chars)  Space: O(total_chars)
    """
    trie = Trie()
    for w in words:
        trie.insert(w)

    best = ""
    for w in sorted(words):                # sorted -> first found is lexicographically smallest
        node = trie.root
        buildable = True
        for ch in w:
            node = node.children[ch]
            if not node.is_end:            # an intermediate prefix is not a real word
                buildable = False
                break
        if buildable and len(w) > len(best):
            best = w
    return best

# Example
print(longest_word(["w","wo","wor","worl","world"]))   # "world"
print(longest_word(["a","banana","app","appl","ap","apply","apple"]))  # "apple"

Complexity: Time O(total_chars + N log N), Space O(total_chars)

Problem 9: Map Sum Pairs (MEDIUM)

Asked at: Amazon, Facebook

Problem: Implement a MapSum that stores key-value pairs and returns the sum of all values whose key starts with a given prefix.

class MapSum:
    """
    Each Trie node accumulates the running sum of values for all
    keys passing through it. On insert of an existing key, propagate
    the delta so prefixes stay correct.
    Time: insert O(L), sum O(L)  Space: O(total_chars)
    """
    def __init__(self):
        self.root = {}
        self.vals = {}

    def insert(self, key, val):
        delta = val - self.vals.get(key, 0)
        self.vals[key] = val
        node = self.root
        node["#"] = node.get("#", 0) + delta
        for ch in key:
            node = node.setdefault(ch, {})
            node["#"] = node.get("#", 0) + delta

    def sum(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return 0
            node = node[ch]
        return node.get("#", 0)

# Example
ms = MapSum()
ms.insert("apple", 3)
print(ms.sum("ap"))      # 3
ms.insert("app", 2)
print(ms.sum("ap"))      # 5

Complexity: Time O(L) per operation, Space O(total_chars)

Problem 10: Stream of Characters (HARD)

Asked at: Google, Amazon

Problem: Given a list of words, support a query() that receives one character at a time and returns True if any suffix of the stream so far spells a word.

class StreamChecker:
    """
    Insert each word REVERSED into the Trie. As characters stream in,
    keep them in a buffer (newest last) and walk the reversed Trie
    from the newest character backward.
    Time: query O(max word length)  Space: O(total_chars)
    """
    def __init__(self, words):
        self.root = {}
        self.stream = []
        self.max_len = max(len(w) for w in words)
        for w in words:
            node = self.root
            for ch in reversed(w):
                node = node.setdefault(ch, {})
            node["$"] = True

    def query(self, letter):
        self.stream.append(letter)
        if len(self.stream) > self.max_len:
            self.stream.pop(0)
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node:
                return False
            node = node[ch]
            if node.get("$"):
                return True
        return False

# Example
sc = StreamChecker(["cd", "f", "kl"])
print([sc.query(c) for c in "abcd"])   # [False, False, False, True]

The reversed-Trie trick is the insight: because we want to match a suffix of the stream, storing words backward lets us walk from the most recent character outward and stop early.

Complexity: Time O(max word length) per query, Space O(total_chars)

How to Recognize a Trie Problem

The pattern signals are consistent across these ten problems. Reach for a Trie when you see any of the following in the problem statement.

The problem mentions prefixes, autocomplete, or "starts with." This is the single strongest signal. A HashMap gives you exact-match lookup but cannot answer "how many words start with this prefix" without scanning everything.

The problem involves a dictionary of words plus repeated lookups or pattern matching against that dictionary. Word Search II, Concatenated Words, and Stream of Characters all share this shape: a fixed word set queried many times, where shared prefixes make a Trie dramatically faster than checking each word independently.

The problem involves wildcards or matching with a single missing character. The Add and Search problem uses the Trie's branching structure to explore all children when it hits a wildcard, which a HashMap cannot do.

The problem is about integers and maximizing or minimizing XOR. This is the bitwise-Trie variant: build the tree over the 32 bits of each number instead of characters, and each node has at most two children.

If none of these appear and you only need exact-string membership, a plain HashSet is simpler and equally fast. The Trie earns its extra complexity precisely when prefixes or branching exploration are involved.

Trie vs HashMap: Decision Guide

When all you need is exact lookup and there are no prefix queries, a HashSet is simpler. When prefixes, autocomplete, or pattern matching are involved, Trie is the right structure.

Trie Optimization Techniques

Path compression (radix tree): if a node has only one child and is not an end node, merge it with its child. Reduces space and speeds up traversal on long, unique suffixes.

Lazy deletion: instead of physically removing nodes on deletion, mark the is_end flag as False. Only compact the tree when memory pressure requires it.

Bitwise Trie: for integer problems (maximum XOR), build a Trie over bits instead of characters. Each node has at most two children (0 and 1). Used in "Maximum XOR of Two Numbers" for O(32*n) solution.

Complexity Summary

Related Articles

• Graph Traversal Patterns 2026
• Dynamic Programming Patterns 2026
• Recursion and Backtracking Patterns 2026
• Must-Do Coding Questions
• Bit Manipulation Questions 2026