Tries (prefix trees)

Why it matters

When many queries ask about prefixes ("which words start with inter?", "is any dictionary word a prefix of this string?"), hashing every prefix or scanning a word list repeats work. A trie shares common prefixes, so each query walks a single path. Tries sit behind autocomplete and spell checking, and in compressed form behind longest-prefix-match lookups such as IP routing tables. Interview problems use them to test node design and to prune searches.

Core ideas

Structure. Each node represents the prefix spelled by the path from the root to it and stores its children plus an end-of-word flag. A word is present only if its last node is marked; reaching a node means only that some stored word has that prefix.

class Node:
    def __init__(self):
        self.children = {}      # char -> Node, or a fixed array of 26
        self.is_word = False

def insert(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, Node())
    node.is_word = True

Pattern: Trie / prefix tree. Insert, exact search and prefix search each cost O(L) for a key of length L, independent of how many words are stored. Memory is one node per distinct prefix, at most the total number of characters inserted. A fixed array of 26 children per node makes each step a direct index but multiplies memory by the alphabet size; a hash map per node saves memory for sparse or large alphabets at some constant-factor cost.

Comparisons. A hash set also answers exact membership in O(L) expected time, but answering "does any word start with this prefix?" requires storing every prefix or scanning. A sorted array with binary search finds the block of words sharing a prefix in O(L log n) time with far less memory, and for a static dictionary that is often enough (Search Suggestions System can be solved either way). A trie wins when there are many prefix queries, incremental insertions, or a search that should stop as soon as a prefix is dead.

Augmentation. Store a count of words passing through each node to answer "how many words start with p" in O(L); Map Sum Pairs stores sums instead and must correct them when a key is overwritten. Storing the complete word at its end node lets a search report it without rebuilding it from the path.

Pruning searches. In Word Search II, walking the grid and the trie together stops a path as soon as it is not a prefix of any remaining word, which is what makes searching for many words at once feasible; removing found words and empty branches prunes further. Wildcard search (Design Add and Search Words) must branch over all children at a wildcard position, so its worst case grows with the alphabet size raised to the number of wildcards.

Variants. Inserting reversed words gives a trie of suffixes: Stream of Characters matches the most recent characters, read backwards, against it. A binary trie over the bits of integers, from the most significant bit down, answers "which stored number maximizes XOR with x?" greedily by preferring the opposite bit at each level: O(B) per query for B-bit numbers. Compressed tries (radix trees) merge chains of single-child nodes to save memory; longest-prefix-match lookups in routing are a classic application.

Common misconceptions

• "Reaching the end of a path means the word exists." Only if the node is marked as a word end; otherwise it is just a prefix.
• "Tries always use less memory than a hash set." Node overhead often makes them larger, especially with fixed-size child arrays.
• "Trie lookups are O(1)." They are O(L) in the key length, as is hashing the key.
• "Every string problem wants a trie." For a few exact lookups a hash set is simpler, and for a static word list sorting plus binary search may be enough.

How to approach it

Reach for a trie when many queries share prefixes or when a search should stop on a dead prefix. Decide the child representation and what each node stores before coding, and state costs in terms of L and the alphabet size. Interviewers typically ask about memory, deletion (unmark the end, then prune nodes that no longer lead to any word) and the alternative with sorting and binary search.