Tries

Overview

A trie (also called a prefix tree) stores a set of strings as paths in a tree. Each edge is one character. Each node stands for the prefix spelled on the way down from the root, and a flag on the node says whether that prefix is also a complete word. Edward Fredkin took the name from the middle of the word retrieval.

Tries fit when a problem asks many questions about prefixes: autocomplete, 'does any word start with this?', replacing words with their shortest root, or searching a grid for many words at once. A hash set answers 'is this exact word stored?' just as fast, but it cannot answer 'which words start with this?' without scanning everything.

The shape of a trie

The words car, card, care and cat share the prefix ca, so they share the first two nodes. A node can be a word end and still have children: car is a word, and card continues below it.

Each node holds two things: a map from character to child, and a boolean is_word. Some problems add more, such as a counter, the full word, or the best suggestions for that prefix.

One walk, three operations

Insert, search and startsWith all walk the key one character at a time from the root. They differ only in what happens when a child is missing and what they check at the end.

• insert(word) — create it — set is_word = True
• search(word) — return False — return is_word
• startsWith(prefix) — return False — return True

A trace

Using the trie above, here is each query, one row per character.

• search("care") — c, a, r, e — c, ca, car, care — care is a word end: True
• search("ca") — c, a — c, ca — ca is not a word end: False
• startsWith("ca") — c, a — c, ca — the path exists: True
• search("cab") — c, a, b — c, ca, no child b — missing child: False
• insert("cars") — c, a, r, s — c, ca, car, new node cars — set cars as a word end

Cost, and when a trie beats a hash set

Let m be the length of the key and L the total number of characters in all stored words.

• Is this exact word stored? — O(m) — O(m) on average (hashing reads the key)
• Does any word start with p? — O(len(p)) — scan all words, or store every prefix
• List words with prefix p — O(len(p) + size of the output) — scan all words
• Words in sorted order — walk children in order — sort first
• Memory — up to L nodes, each with a child map — L characters plus table overhead

The trie wins when prefixes are the question. For exact lookups only, a hash set is simpler and usually uses less memory.

Many words at once: Word Search II

To find which dictionary words appear in a letter grid, checking each word separately repeats the same grid search many times. Instead, build a trie from the words and run one DFS from each cell, walking the grid and the trie together. The trie stops a path the moment no word has that prefix.

Clearing the end mark stops the same word from being reported twice, and removing trie nodes that have no children left keeps later searches from walking dead branches.

Storing the children

• Hash map (dict) — O(1) on average — only the children that exist — any alphabet, sparse nodes
• Fixed array of 26 — O(1), direct index — 26 slots in every node — lowercase a to z only, speed matters
• Compressed (radix or Patricia) — compare a string label per edge — far fewer nodes — long keys with few branches

A compressed trie merges every chain of nodes that have only one child into a single edge labeled with a string. Donald Morrison described this form in 1968 under the name PATRICIA. With slow, slower and slowly, a plain trie needs 8 nodes below the root; a compressed one needs 3.

Tries over bits: maximum XOR

A trie also works on the binary digits of numbers. Insert each number from its highest bit to its lowest. To find the number that gives the largest XOR with x, walk down and at every bit take the opposite bit when that child exists, because a 1 in a higher position is worth more than all lower bits together.

Trace: the trie holds 3 (0011) and 10 (1010), and the query is x = 5 (0101).

• 3 — 0 — 1 — 1 (only 10 has it) — 1000 = 8
• 2 — 1 — 0 — 0 — 1100 = 12
• 1 — 0 — 1 — 1 — 1110 = 14
• 0 — 1 — 0 — 0 — 1111 = 15

The best partner for 5 is 10, and 5 XOR 10 = 15. Each query costs one step per bit, so the whole array takes O(n × bits).

What you will be able to do

• Build a trie from scratch and explain search against startsWith.
• Say when a trie beats a hash set, and when it does not.
• Combine a trie with a grid DFS and prune it as words are found.
• Handle a . wildcard with recursion over the children.
• Use a bitwise trie for maximum XOR problems.

When to use it

• Many prefix queries against one fixed set of words
• Autocomplete or typeahead suggestions for a typed prefix
• Searching a grid for many dictionary words at once (Word Search II)
• Replacing words with their shortest dictionary root
• Pattern search where a wildcard matches any one character
• Longest common prefix of a set of strings
• Maximum XOR of pairs, using a trie over the bits of each number
• Matching a stream of characters against many words (Stream of Characters)

More Coding & DSA topics

• Stacks
• String DP
• Top K Elements
• Topological Sort
• Tree Traversals
• Trees
• Two Heaps
• Two Pointers
• Union Find