# Trie (Prefix Tree) Interview Patterns: Autocomplete, Word Search, Wildcard

Source: https://www.techinterview.org/post/3233463117/trie-prefix-tree-interview-patterns/
Updated: 2026-04-17 · techinterview.org

## Trie (Prefix Tree) Interview Patterns

A Trie (prefix tree) is a tree where each node represents a character in a string, and paths from root to leaf represent words. It enables prefix-based search in O(L) time (L = string length) regardless of dictionary size, making it ideal for autocomplete, spell checking, and IP routing.

- [Coinbase Interview Guide](https://techinterview.org/coinbase-software-engineer-interview/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-software-engineer-interview/)

- [Uber Interview Guide](https://techinterview.org/uber-software-engineer-interview/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-software-engineer-interview/)

- [Apple Interview Guide](https://techinterview.org/apple-software-engineer-interview/)

- [Meta Interview Guide](https://techinterview.org/meta-software-engineer-interview/)

## Basic Trie Implementation


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

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

    def insert(self, word):
        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):
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True
```

Time: O(L) for insert, search, and starts_with (L = length of word/prefix). Space: O(total characters across all inserted words). The dict-based children supports arbitrary alphabets; use a fixed array [None]*26 for lowercase English only (faster lookups).

## Pattern 1: Autocomplete with Top-K Cache


```
class AutocompleteNode:
    def __init__(self):
        self.children = {}
        self.top_k = []  # cached top-K suggestions for this prefix

    def update_top_k(self, word, score, k=10):
        self.top_k.append((score, word))
        self.top_k.sort(reverse=True)
        self.top_k = self.top_k[:k]

def get_suggestions(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node.children: return []
        node = node.children[ch]
    return [word for _, word in node.top_k]
```

Each node caches the top-K most popular words with the given prefix. Lookup is O(L) — traverse to the prefix node, return cached results. Update on insert propagates scores up to ancestors, O(L * K log K).

## Pattern 2: Word Search II (Multiple Words)


```
def find_words(board, words):
    trie = Trie()
    for w in words: trie.insert(w)
    result = set()
    rows, cols = len(board), len(board[0])

    def dfs(node, r, c, path):
        ch = board[r][c]
        if ch not in node.children: return
        next_node = node.children[ch]
        path += ch
        if next_node.is_end: result.add(path)
        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(next_node, nr, nc, path)
        board[r][c] = ch  # restore

    for r in range(rows):
        for c in range(cols):
            dfs(trie.root, r, c, '')
    return list(result)
```

Using a Trie instead of a set for word lookup lets us prune the DFS early: if the current path prefix is not in the Trie, stop immediately. This is significantly faster than checking each word individually for large word lists.

## Pattern 3: Replace Words (Prefix Replacement)


```
def replace_words(dictionary, sentence):
    trie = Trie()
    for root_word in dictionary:
        trie.insert(root_word)

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

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


## Pattern 4: Design Add and Search Words (Wildcard)


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

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

    def search(self, word):
        def dfs(node, i):
            if i == len(word): return node.is_end
            ch = word[i]
            if ch == '.':   # wildcard: try all children
                return any(dfs(child, i+1) for child in node.children.values())
            if ch not in node.children: return False
            return dfs(node.children[ch], i+1)
        return dfs(self.root, 0)
```


## When to Use a Trie

  - Prefix queries: autocomplete, IP routing (longest prefix match)

  - Multiple word search on a board (Word Search II)

  - Prefix replacement or word segmentation

  - Wildcard / regex matching against a dictionary

## Interview Tips

  - Trie beats hash set for prefix queries — hash set requires O(N) scan for prefix match.

  - Top-K cache at each node trades memory for O(L) autocomplete lookups.

  - Word Search II: the early pruning from Trie is the key optimization over brute force.