4.15.0 — Tries: The Pattern

Recognition cue. The problem says prefix, starts with, dictionary, autocomplete, or asks you to match many words at once.

The move. A tree where each edge is a character, so words sharing a prefix share the nodes for it. Lookup costs O(L) for a key of length L, independent of how many keys are stored.

The structure

class TrieNode:
    def __init__(self):
        self.children = {}      # character → TrieNode
        self.is_word = False    # or: self.word = None, storing the whole word

# insert
node = root
for c in word:
    node = node.children.setdefault(c, TrieNode())
node.is_word = True

# walk (shared by search and startsWith)
node = root
for c in prefix:
    if c not in node.children: return None
    node = node.children[c]
return node

search checks the flag on the node it lands on. startsWith does not. Those two differ by exactly one line, and that difference is what the flag exists for.

Trie or hash set?

	trie	hash set
exact lookup	O(L)	O(L) to hash, then O(1)
prefix queries	O(L)	impossible without scanning everything
sorted iteration	free	needs a sort
memory	shares prefixes	stores every key whole

Use a trie only when prefixes matter. For plain membership, a set is simpler and faster.

The three problems

#	Problem	The one insight
4.15.1	Implement Trie ★	The is_word flag separates a word from a prefix
4.15.2	Add and Search Words ★	A wildcard turns the walk into a branching DFS
4.15.3	Word Search II ★	The trie prunes the grid search after one wrong letter

★ marks the Blind 75 subset.

The traps on this pattern

Forgetting the word-end flag. Without it you cannot tell "ca" from "cat", and search becomes startsWith.

Returning True instead of the flag at the end of a search. A path existing is not the same as a word ending there.

Allocating 26 slots per node when the data is sparse. A map costs less and handles any alphabet; an array is faster on dense lowercase data. Say which trade you took.

Forgetting the undo in Word Search II. The board cell must be restored, or later searches find nothing.

Returning early after a match in Word Search II. A longer word may continue through the same cell.

What the interviewer will push on

"Why not a hash set?" No prefix queries.

"What is the complexity?" O(L) per operation, with no dependence on the number of stored words. That independence is the reason the structure exists.

"How would you delete a word?" Clear the flag, then unlink nodes on the way back up while they have no children and are not word endings.

"How would you return all words with a given prefix?" Walk to the prefix node, then DFS below it.

"What is a compressed trie?" Merge chains of single-child nodes into one edge holding a whole string. Much less memory, and it is what IP routing tables actually use (4.13.4, Chapter 5.3.2).

One thing to volunteer: say that lookup cost depends only on key length, never on the number of keys. That is the property that justifies choosing a trie, and most candidates never mention it.

Recall

• A trie is a tree where each edge is a character; words sharing a prefix share nodes.
• Every operation is O(L) in the key length, independent of how many words are stored.
• The word-end flag is what separates search from startsWith — one line of difference.
• Map children for sparse or large alphabets, 26-slot array for dense lowercase. Name the trade.
• A wildcard makes the walk branch, turning it into a DFS that can fail and back out.
• In Word Search II, store the whole word on the terminal node and null it after reporting, and mark the board itself as the visited set with an undo on the way out.
• The trie is the pruning: a letter with no matching child kills the branch in one comparison.

Next: 4.15.1 Implement Trie — build the structure, then the other two problems are variations on searching it.