Concepts / State, data structures and algorithms inside objects / Tries behind prefix APIs

Tries behind prefix APIs

Autocomplete and dictionary objects built on a character tree.

Low-level design conceptState, data structures and algorithms inside objects2 Nov 2026

01The intuition

The problem it solves

You are writing the contacts app on a phone. As the user types "ra", the screen should show Rahul, Rani and Ravi at once. The first version keeps the names in a list and checks every one against the prefix on every keystroke.

class Contacts:
    def __init__(self) -> None:
        self.names: list[str] = []

    def add(self, name: str) -> None:
        self.names.append(name)

    def suggest(self, prefix: str) -> list[str]:
        return [n for n in self.names if n.startswith(prefix)]

With 300 contacts nobody notices. A search box over 10 million product names, with a keystroke every 150 ms, runs 10 million string comparisons per keystroke. The work does not depend on how many answers there are, only on how many names exist. The structure should make the prefix do the narrowing.

Build it one piece at a time

Step one: store names as a tree of characters. Each node has a dictionary from a character to a child node. "ra" is the path root → r → a, and every name starting with "ra" lives in the subtree under that node. Add a flag that says a word ends here.

class Node:
    def __init__(self) -> None:
        self.children: dict[str, "Node"] = {}
        self.is_word = False

class Contacts:
    def __init__(self) -> None:
        self.root = Node()

    def add(self, name: str) -> None:
        node = self.root
        for ch in name:
            node = node.children.setdefault(ch, Node())
        node.is_word = True

Step two: suggest walks the prefix once, then collects words in the subtree. The walk costs one dictionary lookup per typed character, and the collection costs only the size of the answer region.

class Contacts:   # continued
    def suggest(self, prefix: str) -> list[str]:
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return []
        out: list[str] = []
        stack = [(node, prefix)]
        while stack:
            n, text = stack.pop()
            if n.is_word:
                out.append(text)
            for ch, child in n.children.items():
                stack.append((child, text + ch))
        return out

Step three: a real autocomplete wants only the top five, not every match. Store, at each node, the best few completions under it, updated when a word is added or its count changes. The walk then returns the stored list without touching the subtree at all.

class Node:
    def __init__(self) -> None:
        self.children: dict[str, "Node"] = {}
        self.is_word = False
        self.top: list[tuple[int, str]] = []    # (count, word), best first

    def record(self, word: str, count: int, k: int) -> None:
        rest = [t for t in self.top if t[1] != word]
        rest.append((count, word))
        rest.sort(key=lambda t: (-t[0], t[1]))
        self.top = rest[:k]

After adding Rahul, Rani and Ravi the tree looks like this; the node for "ra" already knows its three completions.

Pathis_wordtop (k = 3)
rnoRahul, Rani, Ravi
r → anoRahul, Rani, Ravi
r → a → h → u → lyesRahul
r → a → n → iyesRani
r → a → v → iyesRavi

Why it works

The invariant is that every word is exactly one root-to-flag path, and that the subtree under a node contains all words sharing that node's prefix and no others. Lookup cost is therefore the length of the prefix, not the number of words. With per-node top lists, the invariant extends to: each node's list equals the k best words in its subtree, so a query is a walk plus a copy.

Where it breaks: memory. A node per character with a dictionary each is heavy; a million words of average length 8 is up to 8 million nodes. Compressing chains of single children (a radix tree) or storing children in arrays for small alphabets brings it down. The second trap is updates with per-node top lists: changing one word's count touches every node on its path, length-of-word work, which is fine for words but not for very long keys.

list scan: n × L per query. Trie: Lprefix + answer size per query, independent of n

The trade-off you must say out loud

A trie wins only when prefix is the question. For exact lookups a hash map is simpler and faster; for "contains this substring anywhere" a trie does nothing. Say that you chose a trie because the API is prefix-shaped, mention the memory cost, and offer the radix compression if asked. The follow-up that usually comes next is concurrency: readers walking the tree while a writer inserts, which is where a read-write lock or copy-on-write for the small top lists comes in.

Where it shows up in the 100 Google problems

02Used in these problems