Trie (Prefix Tree)

Intuition

A trie is a rooted tree in which every edge carries one character. The path from the root to a node spells a prefix, so all words starting with "car" live under the same node. A flag on a node says "a word ends here", which distinguishes the word "car" from the mere prefix of "cart".

Why it helps: a hash set answers "is this exact word present?", but not "is any word starting with pre?" or "which words match c.t?". Exact and prefix lookups walk one character at a time, so they cost time proportional to the query length, independent of how many words are stored. A . wildcard must try every child at that depth, so pattern search can visit far more nodes (up to the whole trie).

The same structure over bits instead of letters (a binary trie) stores integers from the highest bit down. Walking it greedily toward the opposite bit finds, for a number x, the stored number that maximizes x XOR y.

When to use it in interviews / OAs

• Prefix queries: startsWith, "how many words have this prefix", autocomplete suggestions.
• Many words searched at once in the same space: "find all dictionary words in a letter grid" (word search II), "replace words with their shortest root", "stream of characters" (insert reversed words).
• Wildcards: ". matches any letter".
• Maximum XOR of two numbers, or of a query with any number from a set (binary trie).
• Word break or concatenated words, where from each position you want every dictionary word that starts there.

Template

Trie with prefix counts and wildcard search

class TrieNode:
    __slots__ = ("children", "is_word", "count")

    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_word = False
        self.count = 0  # how many inserted words pass through this node


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

    def insert(self, word: str) -> None:
        node = self.root
        node.count += 1
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
            node.count += 1
        node.is_word = True

    def _walk(self, s: str) -> TrieNode | None:
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def count_prefix(self, prefix: str) -> int:
        node = self._walk(prefix)
        return node.count if node else 0

    def search_wildcard(self, pattern: str) -> bool:
        # "." matches any single character
        stack = [(self.root, 0)]
        while stack:
            node, i = stack.pop()
            if i == len(pattern):
                if node.is_word:
                    return True
                continue
            ch = pattern[i]
            if ch == ".":
                stack.extend((child, i + 1) for child in node.children.values())
            elif ch in node.children:
                stack.append((node.children[ch], i + 1))
        return False

Word search II: a trie drives the grid DFS

Searching each word separately repeats work for shared prefixes. Instead, walk the board once while walking the trie, stop as soon as the current path is not a prefix of any word, and delete branches that are exhausted.

def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    root: dict = {}
    for w in words:
        node = root
        for ch in w:
            node = node.setdefault(ch, {})
        node["$"] = w  # end marker stores the word (board holds lowercase letters)
    rows, cols, found = len(board), len(board[0]), []

    def dfs(r: int, c: int, parent: dict) -> None:
        ch = board[r][c]
        node = parent[ch]
        if "$" in node:
            found.append(node.pop("$"))  # pop: report each word once
        board[r][c] = "#"  # used on the current path
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node:
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node:  # nothing left below: prune this branch for good
            parent.pop(ch)

    for r in range(rows):
        for c in range(cols):
            if board[r][c] in root:
                dfs(r, c, root)
    return found

Binary trie: maximum XOR of two numbers

def max_xor_pair(nums: list[int], bits: int = 31) -> int:
    # nums are non-negative and below 2**bits
    root: list = [None, None]
    best = 0
    for x in nums:
        node = root
        for b in range(bits - 1, -1, -1):  # insert x, highest bit first
            bit = (x >> b) & 1
            if node[bit] is None:
                node[bit] = [None, None]
            node = node[bit]
        node, cur = root, 0
        for b in range(bits - 1, -1, -1):  # query: prefer the opposite bit at every level
            bit = (x >> b) & 1
            if node[bit ^ 1] is not None:
                cur |= 1 << b
                node = node[bit ^ 1]
            else:
                node = node[bit]
        best = max(best, cur)
    return best

The greedy is safe because a 1 in a higher bit outweighs every lower bit combined.

Complexity

Insert, search and prefix queries are O(L) for a string of length L. Memory is O(total characters) nodes; with fixed arrays of 26 children per node it becomes O(26 * total characters), faster but heavier. The binary trie costs O(n * bits) time and memory. Word search II is bounded by the number of grid paths that stay inside the trie, which the pruning keeps small in practice.

Common pitfalls

• Prefix vs. word. Reaching the node for "app" does not mean "app" was inserted; check is_word.
• Counting duplicates. With repeated inserts, decide whether count should count multiplicity (as here) or distinct words.
• Memory blow-up with one 26-slot array per node in Python; dictionaries (or __slots__) keep nodes small.
• Word search II duplicates and timeouts. Without popping the end marker the same word is reported twice; without pruning exhausted branches large boards time out.
• Binary trie bit width. Use enough bits for the maximum value, and handle negative numbers separately (offset them or treat the sign bit specially).
• Deep recursion if words are very long; walk iteratively as in _walk and search_wildcard.

Interview variations

• Implement Trie / design add-and-search words. The class above.
• Replace words with roots. Walk each word and stop at the first node with is_word.
• Search suggestions / autocomplete. Keep up to three lexicographically smallest words at each node (insert words in sorted order), or DFS in alphabetical order.
• Map sum pairs. Store a running sum at each node and adjust it by the delta when a key is overwritten.
• Stream of characters. Insert reversed words; for each new letter walk the trie over the most recent letters, newest first.
• Maximum XOR with an element under a limit. Sort queries by limit, insert numbers in increasing order, and query the binary trie (offline processing).
• Many patterns in one text. Adding failure links turns the trie into the Aho-Corasick automaton.