Tries: The Data Structure Behind Autocomplete

A trie (pronounced “try”, from retrieval) is a tree where each edge is labeled with a character and each path from the root spells a prefix of some stored string. Tries are the data structure behind autocomplete, spell checkers, IP routing tables, and many word-game solvers. They are simple to implement once you have seen the node layout, and they unlock a class of prefix queries that hash maps cannot answer efficiently.

Node structure

Each node holds:

1. A map (or fixed-size array) from character to child node.
2. A boolean marking whether a complete word ends at this node.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

If your alphabet is fixed and small, an array indexed by ord(c) - ord('a') is faster but uses 26 slots per node. A dictionary is more memory-efficient for sparse trees and works for arbitrary characters.

Insert, search, prefix

The three core operations share the same shape. Walk down the tree one character at a time. Insert creates missing children; search returns false on a missing child; startsWith returns true as long as the walk completes.

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

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

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self.root
        for c in s:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

Each operation runs in O(L) time where L is the length of the query string. The runtime is independent of how many words are stored, which is the trie’s signature advantage.

Space tradeoffs

Tries trade memory for query power. In the worst case a trie storing N words of average length L over alphabet size A uses O(N * L) nodes, each with up to A child slots. Compare with:

• Hash set: O(total characters) memory, O(L) average insert/lookup, but no prefix queries at all.
• Sorted array + binary search: O(total characters) memory, O(L log N) lookup, supports prefix queries via two binary searches.

If you need prefix counting, autocomplete, or lexicographic traversal, the trie’s flat O(L) operations are worth the extra memory. For pure membership testing on long strings, a hash set is usually smaller and faster. The general comparison framework comes from Big-O Notation Explained.

Problem 1: Implement longest common prefix

Given an array of strings, return the longest common prefix.

Insert every string. Walk down from the root while each node has exactly one child and is not the end of a shorter word. The path you walk is the longest prefix shared by all inputs.

def longest_common_prefix(words):
    if not words:
        return ""

    trie = Trie()
    for w in words:
        trie.insert(w)

    prefix = []
    node = trie.root
    while len(node.children) == 1 and not node.is_end:
        c, child = next(iter(node.children.items()))
        prefix.append(c)
        node = child
    return "".join(prefix)

Total work is O(total characters) for building plus O(L_min) to walk. There is a simpler character-by-character solution without a trie, but the trie approach generalizes to “longest prefix shared by at least k strings” with a small modification.

Problem 2: Word search II

Given an m x n board of letters and a list of words, return all words that can be formed by sequentially adjacent cells (no reuse).

A naive solution runs DFS for every word, which is too slow when there are many words. The trie-based solution flips it: insert every word into a trie, then DFS from each cell, descending the trie in lockstep. The moment the current prefix is not in the trie, prune the branch.

def find_words(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for c in w:
            node = node.children.setdefault(c, TrieNode())
        node.word = w  # store the full word at the terminal node

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

    def dfs(r, c, node):
        ch = board[r][c]
        nxt = node.children.get(ch)
        if not nxt:
            return
        if hasattr(nxt, 'word') and nxt.word:
            found.append(nxt.word)
            nxt.word = None  # avoid duplicates

        board[r][c] = '#'
        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, nxt)
        board[r][c] = ch

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

The trie shares prefix work across all candidate words, so the search visits the board at most O(m * n * 4^L) times where L is the max word length, but pruning is so aggressive that the practical performance is much better. This pattern, search plus pruning, is the same one explored in DFS over graphs; see Graphs: BFS and DFS.

Variants worth knowing

• Compressed trie (radix tree): collapse single-child chains into one edge labeled with a substring. Saves memory at the cost of more careful splitting on insert.
• Suffix trie / suffix automaton: store every suffix of a single string for fast substring queries.
• Ternary search trie: stores each node as a small BST over its children, saving space when the alphabet is large and sparse.

Common pitfalls

• Forgetting the is_end flag. Without it you cannot distinguish “car” being stored from “car” merely being a prefix of “cart”.
• Mutating children during iteration. When deleting a word, only remove children that have no further descendants.
• Choosing the wrong child container. Default to a dict; switch to a fixed-size array only after profiling shows the dict overhead matters.

Wrap up

A trie is essentially a tree-shaped hash map keyed by character. Insertion, lookup, and prefix queries are all O(L), independent of the dictionary size. The price is memory and a bit more code than a hash set. For autocomplete, prefix counting, word games, and any problem where many strings share prefixes, that price is the best deal in algorithm design.