# Trie Interview Patterns

Source: https://www.techinterview.org/post/3233466827/trie-patterns/
Updated: 2026-07-05 · techinterview.org

Trie (prefix tree) problems appear frequently in coding interviews. This guide covers the core patterns with Python implementations you can adapt to any trie problem.

## Trie Node Structure and Basic Operations (LC 208)

Every trie implementation starts with a node class and the three core operations: insert, search, and startsWith.


```
class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False

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

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True
```


Time: O(m) for all operations where m is the word length. Space: O(m * n) total for n words of average length m.

## Word Dictionary with Wildcards (LC 211)

When '.' can match any character, use DFS through the trie trying all children at wildcard positions.


```
class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        return self._dfs(word, 0, self.root)

    def _dfs(self, word: str, i: int, node: TrieNode) -> bool:
        if i == len(word):
            return node.is_end
        ch = word[i]
        if ch == '.':
            # Try all children
            for child in node.children.values():
                if self._dfs(word, i + 1, child):
                    return True
            return False
        else:
            if ch not in node.children:
                return False
            return self._dfs(word, i + 1, node.children[ch])
```


## Word Search II (LC 212) - DFS on Board with Trie Pruning

Build a trie from all words, then DFS from every board cell. The key optimization: remove matched words from the trie to avoid duplicate results and speed up subsequent searches.


```
class TrieNodeWS:
    def __init__(self):
        self.children = {}
        self.word = None  # store complete word at end node

class Solution:
    def findWords(self, board, words):
        root = TrieNodeWS()
        for w in words:
            node = root
            for ch in w:
                if ch not in node.children:
                    node.children[ch] = TrieNodeWS()
                node = node.children[ch]
            node.word = w

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

        def dfs(r, c, node):
            ch = board[r][c]
            if ch not in node.children:
                return
            next_node = node.children[ch]
            if next_node.word:
                results.append(next_node.word)
                next_node.word = None  # remove to avoid duplicates

            board[r][c] = '#'  # mark visited
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                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] = ch  # restore

            # Prune: remove leaf nodes with no remaining words
            if not next_node.children and not next_node.word:
                del node.children[ch]

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

        return results
```


The pruning step (deleting empty leaf nodes) is what separates a solution that times out from one that passes. After finding a word, its trie path becomes dead weight - remove it.

## Auto-Complete System Design

A production auto-complete system uses a trie augmented with frequency counts and top-k results cached at each node.


```
import heapq

class AutocompleteNode:
    def __init__(self):
        self.children = {}
        self.freq = 0
        # Cache top-3 (word, freq) pairs at this node
        self.top_k = []  # min-heap by freq

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.root = AutocompleteNode()
        self.current = []  # characters typed so far
        for s, t in zip(sentences, times):
            self._insert(s, t)

    def _insert(self, sentence: str, freq: int):
        node = self.root
        for ch in sentence:
            if ch not in node.children:
                node.children[ch] = AutocompleteNode()
            node = node.children[ch]
            # Update top-k at each node along the path
            self._update_topk(node, sentence, freq)
        node.freq += freq

    def _update_topk(self, node, sentence, freq):
        # Keep a min-heap of size 3
        for i, (f, s) in enumerate(node.top_k):
            if s == sentence:
                node.top_k[i] = (freq, sentence)
                heapq.heapify(node.top_k)
                return
        if len(node.top_k) < 3:
            heapq.heappush(node.top_k, (freq, sentence))
        elif freq > node.top_k[0][0]:
            heapq.heapreplace(node.top_k, (freq, sentence))

    def input(self, c: str):
        if c == '#':
            sentence = ''.join(self.current)
            self._insert(sentence, 1)
            self.current = []
            return []
        self.current.append(c)
        node = self.root
        for ch in self.current:
            if ch not in node.children:
                return []
            node = node.children[ch]
        return [s for f, s in sorted(node.top_k, reverse=True)]
```


Design notes: For real systems, the top-k cache makes each prefix lookup O(1) instead of O(subtree size). Trade-off: inserts become slower because you update cached results at every prefix node. With billions of queries, precompute top-k offline and store in Redis.

## Bitwise Trie for XOR Maximum (LC 421)

Insert numbers bit by bit from MSB (bit 31) to LSB (bit 0). To find the number that maximizes XOR with a query, greedily go to the opposite bit at each level.


```
class BitwiseTrieNode:
    def __init__(self):
        self.children = [None, None]  # index 0 or 1

class Solution:
    def findMaximumXOR(self, nums) -> int:
        root = BitwiseTrieNode()

        def insert(num):
            node = root
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                if not node.children[bit]:
                    node.children[bit] = BitwiseTrieNode()
                node = node.children[bit]

        def query(num) -> int:
            node = root
            xor = 0
            for i in range(31, -1, -1):
                bit = (num >> i) & 1
                want = 1 - bit  # go opposite to maximize XOR
                if node.children[want]:
                    xor |= (1 << i)
                    node = node.children[want]
                else:
                    node = node.children[bit]
            return xor

        for n in nums:
            insert(n)

        return max(query(n) for n in nums)
```


This runs in O(32n) = O(n) time. The bitwise trie has at most 32 * n nodes for 32-bit integers.

## Replace Words with Root (LC 648)

Build a trie from all roots. For each word in the sentence, walk the trie - if you hit an end node before consuming the full word, replace with the root.


```
class Solution:
    def replaceWords(self, dictionary, sentence: str) -> str:
        root = TrieNode()
        for word in dictionary:
            node = root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.is_end = True

        def replace(word):
            node = root
            for i, ch in enumerate(word):
                if ch not in node.children:
                    return word  # no root found
                node = node.children[ch]
                if node.is_end:
                    return word[:i+1]  # replace with root
            return word

        return ' '.join(replace(w) for w in sentence.split())
```


## Pattern Recognition: Trie vs Hash Set

Use a trie when the problem involves prefix queries. Use a hash set when you need exact membership checks.

| Signal in problem | Data structure |
| --- | --- |
| "starts with", "prefix", "autocomplete" | Trie |
| "common prefix", "replace by shortest prefix" | Trie |
| "find all words matching pattern" | Trie + DFS |
| "exists in set", "seen before" | Hash set |
| "maximize XOR" | Bitwise trie |
| No prefix queries needed | Hash set (simpler, faster) |

Key trie trade-offs: faster prefix queries than hash set, but higher memory usage (each character is a node). For small alphabets (26 letters) this is fine. For Unicode, use a hash map for children instead of a fixed array.

Meta coding interviews frequently test trie problems. See common patterns for [Meta interview: trie and string search problems](https://www.techinterview.org/post/3233460272/meta-interview-guide-2026-facebook-instagram-whatsapp-engineering/).

Apple coding rounds include trie and string prefix problems. See patterns for [Apple interview: trie and autocomplete system design](https://www.techinterview.org/post/3233460277/apple-interview-guide-2026-ios-systems-hardware-software-integration-and-icloud-architecture/).

LinkedIn engineering interviews test trie and autocomplete patterns. See common questions for [LinkedIn interview: trie and search problems](https://www.techinterview.org/post/3233460278/linkedin-interview-guide-2026-social-graph-engineering-feed-ranking-and-professional-network-scale/).