Tries and Autocomplete: Prefix Trees in Action

Projectsmedium25 min
Ask Cairnly about this lesson
On this page

What you will learn

  • Understand the trie data structure and its O(L) insert/search/prefix operations
  • Implement a trie with insert, search, and startsWith methods
  • Build autocomplete functionality on top of a trie
  • Solve "word search II" and "design search suggestions system"

Why this matters

Tries power every search bar autocomplete, spell checker, and IP routing table in production. In interviews, trie problems test whether you can implement a tree structure from scratch rather than relying on library data structures. They also appear in word-search grid problems where a trie prunes the search space dramatically.

What is a trie?

A trie (prefix tree) is a tree where each edge represents a character. Paths from root to marked nodes represent stored words. Shared prefixes share the same path, saving space and enabling fast prefix lookups.

text
          root
         / | \
        a  b  c
       /      |
      p       a
     / \      |
    p   e     t   <- "cat" ends here
    |         
    l         
    e   <- "apple" ends here, "ape" ends at 'e' above

Implementation (LC 208)

python
class TrieNode:
    def __init__(self):
        self.children = {}      # char -> TrieNode
        self.is_end = False     # marks complete words
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(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):
        """Returns True if the exact word exists."""
        node = self._find_node(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix):
        """Returns True if any word starts with the given prefix."""
        return self._find_node(prefix) is not None
 
    def _find_node(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

Insert/Search/StartsWith: O(L) where L is the word/prefix length. Space: O(total characters across all words) in the worst case.

Building autocomplete

Given a prefix, return all words in the trie that start with it.

python
def autocomplete(self, prefix):
    node = self._find_node(prefix)
    if not node:
        return []
    results = []
    self._collect_words(node, prefix, results)
    return results
 
def _collect_words(self, node, current, results):
    if node.is_end:
        results.append(current)
    for char, child in node.children.items():
        self._collect_words(child, current + char, results)
python
trie = Trie()
for word in ["apple", "app", "ape", "application", "bat", "batch"]:
    trie.insert(word)
 
print(trie.autocomplete("app"))  # ["app", "apple", "application"]
print(trie.autocomplete("ba"))   # ["bat", "batch"]

Walkthrough: Word Search II (LC 212)

Given a board of characters and a list of words, find all words that can be formed by adjacent cells. A trie turns this from "run DFS for each word" into "run DFS once, guided by the trie."

python
def find_words(board, words):
    trie = Trie()
    for w in words:
        trie.insert(w)
 
    rows, cols = len(board), len(board[0])
    result = set()
 
    def dfs(r, c, node, path):
        if node.is_end:
            result.add(path)
            node.is_end = False  # avoid duplicates
 
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        char = board[r][c]
        if char not in node.children:
            return
 
        board[r][c] = '#'  # mark visited
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            dfs(r+dr, c+dc, node.children[char], path + char)
        board[r][c] = char  # restore
 
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, trie.root, "")
    return list(result)

Key insight: Without a trie, you'd run separate DFS for each word: O(words * rows * cols * 4^L). With a trie, you run one DFS that simultaneously checks all words: the trie prunes branches where no word can be formed.

When to use a trie

SignalUse case
"Find all words with prefix X"Trie with DFS collection
"Autocomplete / search suggestions"Trie + prefix traversal
"Word search on a grid"Trie-guided DFS
"Count words with prefix"Trie with prefix count stored at each node
"Longest common prefix"Trie traversal until a branch point

Try it yourself

  1. LC 208 - Implement Trie: Build insert, search, and startsWith from scratch.
  2. LC 212 - Word Search II: Implement the trie-guided DFS. Compare runtime with the naive word-by-word approach.
  3. LC 1268 - Search Suggestions System: Return the top 3 suggestions for each prefix as the user types.
  4. Extension: Add a delete(word) method to your trie. What edge cases arise?
python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
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._find_node(word)
        return node is not None and node.is_end
 
    def starts_with(self, prefix):
        return self._find_node(prefix) is not None
 
    def _find_node(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node
 
    def autocomplete(self, prefix):
        node = self._find_node(prefix)
        if not node:
            return []
        results = []
        def collect(n, path):
            if n.is_end:
                results.append(path)
            for ch, child in sorted(n.children.items()):
                collect(child, path + ch)
        collect(node, prefix)
        return results
 
# --- Test ---
trie = Trie()
for w in ["apple", "app", "ape", "application", "bat", "batch"]:
    trie.insert(w)
 
print("Search 'app':", trie.search("app"))       # True
print("Search 'ap':", trie.search("ap"))          # False
print("Prefix 'ap':", trie.starts_with("ap"))     # True
print("Autocomplete 'app':", trie.autocomplete("app"))  # ['app', 'apple', 'application']
print("Autocomplete 'ba':", trie.autocomplete("ba"))    # ['bat', 'batch']

Checklist

  • I can implement a TrieNode and Trie class from memory
  • I understand the O(L) complexity for insert, search, and prefix queries
  • I can extend a trie with autocomplete (DFS collection)
  • I understand how a trie prunes the search space in Word Search II
  • I can explain when a trie is better than a hash set of words

Common mistakes

  • Using an array of 26 instead of a dictionary: Arrays are fine for lowercase English letters, but dictionaries are more flexible and just as fast in Python. Use arrays only if the interviewer specifically requests it.
  • Forgetting is_end: Without it, search("app") returns True even if only "apple" was inserted, because the prefix path exists.
  • Not pruning in Word Search II: The whole point of using a trie is to avoid exploring paths where no word can be formed. If you don't check char not in node.children, you lose the performance benefit.
  • Memory overhead: Each node stores a dictionary. For very large dictionaries, consider compressed tries (radix trees) as a follow-up discussion.

Quick quiz

Q: What is the time complexity of searching for a word of length L in a trie containing N words?

How to explain it in an interview

"A trie stores words character by character in a tree. To search, I walk down the tree following one character per step, so search is O(L) regardless of how many words are stored. For autocomplete, I traverse to the prefix node then DFS to collect all words below it. The big advantage over a hash set is prefix queries: startsWith is O(L) with a trie but O(N * L) if you scan every word in a hash set. For Word Search II, a trie lets me run a single DFS over the grid, pruning branches that can't lead to any word."