Prefix Tree

Tries (Prefix Trees)

A trie, short for retrieval tree and also called a prefix tree, formalized in LeetCode 208, is a data structure purpose-built for storing and searching strings. Unlike a hash map, which treats each string as an opaque key, a trie exploits the shared prefixes between strings to give you something a hash map cannot: the ability to answer prefix queries in $O(L)$ time, where L is the length of the query string, completely independent of how many strings are stored.

The Data Structure

Each node in a trie represents a single character position along some path from the root. The root itself represents the empty string. A node holds two things: a dictionary mapping characters to child nodes, and a boolean flag marking whether some inserted word ends at that node.

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

The trie itself is just a wrapper around a root node:

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

Insert, Search, and StartsWith

Inserting a word means walking the trie one character at a time, creating nodes where they don't yet exist, and setting is_end = True on the final node. Searching for a word is the same walk, but instead of creating nodes you return False if a child is missing, and at the end you check the is_end flag. The starts_with query is identical to search except you skip the is_end check, because you only care whether any path through the trie begins with that prefix.

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(word)
    return node is not None and node.is_end

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

def _find(self, prefix):
    node = self.root
    for ch in prefix:
        if ch not in node.children:
            return None
        node = node.children[ch]
    return node

Walked Example

Suppose you insert the words "app", "apple", and "apt". After insertion the trie looks like this:

• root → a → p → p [end] → l → e [end]
• root → a → p → t [end]

The a and p nodes are shared by all three words. Now:

• search("app") follows a→p→p, finds is_end = True, returns True.
• search("ap") follows a→p, but is_end = False, returns False.
• starts_with("ap") follows a→p, node exists, returns True.
• search("apex"): after a→p, there is no e child, returns False.

Every query touches at most L nodes. There is no hashing, no collision handling, and no dependence on the total number of stored strings.

Why $O(L)$ Lookup Matters

A hash map gives $O(L)$ average-case lookup for a single string, but it cannot answer "does any stored word begin with this prefix?" without iterating all keys. A trie answers that in the same $O(L)$ time as an exact match. For autocomplete systems that must rapidly narrow a word list as the user types, this is exactly the property you need.

Space usage is $O(total characters across all words)$, which in the worst case (no shared prefixes) is the same as storing all words in a list, but in practice the shared-prefix structure saves substantial memory.

Application: Word Search II (Board + Word List)

LeetCode 212 gives you a grid of letters and a list of target words, and asks which words can be spelled by traversing adjacent cells. The naive approach, running a DFS for each word separately, is prohibitively slow when the word list is large.

The trie approach builds a trie from all target words, then runs a single DFS across the board. At each cell you follow the trie one character at a time. If the current cell's character has no child in the trie node you're holding, you immediately backtrack, since the trie prunes entire subtrees of the search space at once. When you reach a node with is_end = True, you've found a word. To avoid reporting duplicates, clear the is_end flag after recording it.

def find_words(board, words):
    trie = Trie()
    for w in words:
        trie.insert(w)

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

    def dfs(r, c, node, path):
        ch = board[r][c]
        if ch not in node.children:
            return
        next_node = node.children[ch]
        path.append(ch)
        if next_node.is_end:
            result.append("".join(path))
            next_node.is_end = False  # deduplicate
        board[r][c] = "#"  # mark visited
        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, next_node, path)
        board[r][c] = ch  # restore
        path.pop()

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, trie.root, [])
    return result

Wildcard Matching with '.'

With LeetCode 211, when a search pattern can contain '.' to match any single character, you cannot follow a single child pointer. Instead you recurse into all children at that position. This is naturally expressed as a recursive DFS through the trie:

def search_with_wildcard(self, word):
    def dfs(node, i):
        if i == len(word):
            return node.is_end
        ch = word[i]
        if ch == ".":
            return any(dfs(child, i + 1) for child in node.children.values())
        if ch not in node.children:
            return False
        return dfs(node.children[ch], i + 1)
    return dfs(self.root, 0)

Binary Tries for XOR Problems

A binary trie stores integers bit by bit (most significant bit first), with children keyed on 0 and 1 instead of characters. This lets you find the number in a set that maximizes XOR with a query value: for each bit of the query, greedily follow the opposite bit if that child exists (since XOR of opposite bits is 1). This gives $O(32)$ lookup, effectively $O(1)$, for maximum XOR queries over a large set of integers.

Replace Words with a Trie

LC 648 gives you a dictionary of root words and a sentence. For each word in the sentence, replace it with its shortest matching root. A trie built from the roots makes this efficient: for each word, walk the trie character by character and stop as soon as you hit a node with is_end = True, which is the shortest prefix match.

def replaceWords(dictionary, sentence):
    trie = Trie()
    for root in dictionary:
        trie.insert(root)

    def find_root(word):
        node = trie.root
        for i, ch in enumerate(word):
            if ch not in node.children:
                break
            node = node.children[ch]
            if node.is_end:
                return word[:i + 1]
        return word

    return " ".join(find_root(w) for w in sentence.split())

Building the trie is $O(\sum |root|)$. Each word lookup is $O(L)$ where L is the word length (or shorter if a root is found early). Total time is linear in the size of the input.

Map Sum Pairs

LC 677 asks you to build a data structure that maps string keys to integer values, and supports a sum query returning the total value of all keys that start with a given prefix. A trie where each node stores the cumulative sum of all values passing through it handles this naturally.

On insert, if a key already exists, compute the delta (new value minus old value); otherwise the delta is the new value. Walk the trie from root to the end of the key, adding the delta to every node along the path. For sum, walk to the prefix node and return its stored sum.

class MapSum:
    def __init__(self):
        self.root = {}
        self.map = {}  # key -> current value

    def insert(self, key: str, val: int) -> None:
        delta = val - self.map.get(key, 0)
        self.map[key] = val
        node = self.root
        for ch in key:
            node = node.setdefault(ch, {"_sum": 0})
            node["_sum"] += delta

    def sum(self, prefix: str) -> int:
        node = self.root
        for ch in prefix:
            if ch not in node:
                return 0
            node = node[ch]
        return node.get("_sum", 0)

Insert and sum are both $O(L)$. The map dictionary tracks current values so that re-inserting a key with a different value correctly adjusts the path sums by the delta rather than double-counting.

Maximum XOR of Two Numbers (Binary Trie)

LC 421 asks for the maximum XOR of any pair in an array. The binary trie approach inserts each number bit by bit from the most significant bit down. Then for each number, you greedily walk the trie choosing the opposite bit at each level (since XOR of opposite bits is 1), falling back to the same bit if the opposite child does not exist.

def findMaximumXOR(nums):
    root = {}
    HIGH_BIT = 31

    def insert(num):
        node = root
        for i in range(HIGH_BIT, -1, -1):
            bit = (num >> i) & 1
            if bit not in node:
                node[bit] = {}
            node = node[bit]

    def query(num):
        node = root
        xor_val = 0
        for i in range(HIGH_BIT, -1, -1):
            bit = (num >> i) & 1
            toggled = 1 - bit
            if toggled in node:
                xor_val |= (1 << i)
                node = node[toggled]
            else:
                node = node[bit]
        return xor_val

    max_xor = 0
    for num in nums:
        insert(num)
        max_xor = max(max_xor, query(num))
    return max_xor

Each insert and query is $O(32)$, constant time per number. Total time is $O(32n) = O(n)$, and space is $O(32n)$ for the trie nodes.

Complexity Summary

• Insert: $O(L)$ time, $O(L)$ space in the worst case (new path with no shared prefix)
• Search / StartsWith: $O(L)$ time, $O(1)$ extra space
• Overall space: $O(N \cdot L)$ where N is the number of words and L is average word length, though shared prefixes reduce this considerably in practice

Recognizing this pattern

You're probably looking at a trie when:

• The problem stores a large dictionary of strings and repeatedly asks "is this word/prefix present?" with many lookups against the same set and heavy prefix overlap.
• You need to search a board or graph for any of K words simultaneously, and re-running KMP per word would be too slow.
• The problem asks for autocomplete, longest common prefix, or all words starting with a given prefix.
• You're maximizing XOR or matching bit patterns against a set of integers, where a bitwise trie of depth 32 is the standard tool.

Common templates:

• Standard insert/search/startsWith: dict-of-children with an end-of-word flag. Example: Implement Trie (Prefix Tree).
• Trie + DFS over a board: descend the trie alongside grid exploration, prune dead branches. Example: Word Search II.
• Wildcard search via DFS: recurse over all children when the query character is .. Example: Design Add and Search Words Data Structure.
• Bitwise trie for max XOR: insert each number bit-by-bit from MSB, greedily pick the opposite bit at query time. Example: Maximum XOR of Two Numbers in an Array.