Portfolio/Learn/Tries: Prefix Trees for Fast String Operations
Algorithms & DSIntermediate

Tries: Prefix Trees for Fast String Operations

Build a Trie from scratch and use it for autocomplete, spell checking, word search, and IP routing. Understand when tries beat hash maps for string problems.

13 min read
March 6, 2026
TriePrefix TreeStringsAutocompletePython

What Is a Trie?

A Trie (prefix tree) stores strings character by character in a tree structure. Each node represents a character, and paths from root to nodes represent prefixes. Tries enable O(L) insert, search, and prefix lookup where L is the string length — independent of how many strings are stored. This makes them ideal for autocomplete, spell checking, and prefix-based filtering.

Implementation

python
class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False


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

    def insert(self, word: str) -> None:
        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: str) -> bool:
        """Returns True if word is in the trie."""
        node = self._find_node(word)
        return node is not None and node.is_end

    def starts_with(self, prefix: str) -> bool:
        """Returns True if any word starts with the prefix."""
        return self._find_node(prefix) is not None

    def _find_node(self, prefix: str) -> TrieNode | None:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def autocomplete(self, prefix: str, limit: int = 10) -> list[str]:
        """Return all words starting with prefix."""
        node = self._find_node(prefix)
        if not node:
            return []

        results = []

        def dfs(current: TrieNode, path: str):
            if len(results) >= limit:
                return
            if current.is_end:
                results.append(path)
            for char, child in sorted(current.children.items()):
                dfs(child, path + char)

        dfs(node, prefix)
        return results

Trie vs Hash Map: Use a trie when you need prefix queries (autocomplete, prefix counting). Use a hash map when you only need exact-match lookups. Tries use more memory but enable operations hash maps can't do efficiently.

Word Search in a Grid

A classic problem: given a board of characters and a list of words, find all words that can be formed by traversing adjacent cells. Building a trie from the word list lets you prune the search early — if no word starts with the current prefix, stop exploring.

python
def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    """Find all words from the list that exist in the board."""
    trie = Trie()
    for word in words:
        trie.insert(word)

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

    def dfs(r: int, c: int, node: TrieNode, path: str):
        if node.is_end:
            result.add(path)

        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
        next_node = node.children[char]
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            dfs(r + dr, c + dc, next_node, path + char)
        board[r][c] = char  # Unmark

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

    return list(result)

For the word search problem, optimize by removing words from the trie as you find them and pruning empty branches. This prevents redundant exploration on large word lists.

More Articles