Tries
A trie (from retrieval, said either "try" or "tree") stores a set of
strings by spelling each one out as a path from the root, one character per
edge, with every string that shares a prefix sharing that prefix's path. It
trades the O(1)-average lookup of a hash set for something a hash set
cannot do at all: answer "what starts with this prefix" without touching
every string you have stored.
1. A tree whose edges are characters
Insert cat, car, card, and dog. cat and car share the path c -> a
and only fork at the third letter; card continues past car; dog shares
nothing with the others and gets its own branch from the root.
A hash set node "is" the
string it holds; a trie node is just a fork in the road. Reading cat back
out means walking root -> c -> a -> t and concatenating the edge labels you
crossed - the node at the end of that walk does not know its own name.
2. Building and searching
The fastest correct implementation needs no custom class at all: a
defaultdict whose values are themselves defaultdicts builds the entire
branching structure for you, one line per insert.
The explicit version makes the same structure visible as a class, which is worth seeing once because most interview solutions are written this way:
search and starts_with differ by exactly one check: starts_with only
needs the walk to succeed, search additionally needs the node it lands on
to be a real word's end, not just a fork other words pass through.
3. The end-of-word flag
Every node in the diagram above sits on some path, but only four of them are the end of a stored word. Without a flag marking that, the trie cannot tell "this string was inserted" apart from "this string is a prefix of something that was inserted" - and those are different questions with different answers.
A node with children is not automatically a word, and search must check
the flag, not just the walk. If insert never sets is_word for ca, then
"ca" in words must return False even though every character of ca has a
node - _walk("ca") succeeds and returns a real node, but that node's
is_word is False. This is exactly why search is two checks
(_walk succeeds and is_word) while starts_with is only one. Confusing
them makes every prefix of every inserted word look like it was inserted too.
4. What a node actually holds
is_word answers "was this exact string inserted". It cannot answer "how
many stored words start here", and it cannot tell you whether deleting a word
is allowed to remove a node. One more integer per node does both.
count is how many inserted words pass through this prefix. Every insert
walks a path and raises the count on every node it touches, so a node's count
is the size of the subtree of words underneath it, already computed.
Maintaining it is one line inside the loop that was already walking the path:
count_with_prefix is O(L) and nothing more. Without the field the same
question needs _walk plus a full DFS of the subtree underneath, which is
O(number of matching words * their length) - fine when you wanted the words
anyway, wasteful when you only wanted the number.
The second thing count buys is a correct delete. Removing a word means
walking down, decrementing, and then discarding only the nodes no surviving
word still needs:
A node is safe to discard when its count reaches zero, not when it happens
to be childless - and the scan for that zero runs top-down, not bottom-up.
Counts only shrink as you descend, so if a node's count is zero every node
below it is zero too; cutting at the deepest zero leaves a dead chain of
zero-count ancestors still hanging off the trie. Cutting at the shallowest
zero takes the whole dead subtree in one unlink. Delete card from the trie above and the node for car
drops to count 1 but keeps is_word - discarding it because the d below it
went away would silently delete car too. The mirror bug is deleting a word
that was never inserted: without the search guard at the top, every node
along its path gets decremented anyway, and counts that should have stayed at
1 go to 0, so the next delete prunes a live branch.
Every node below is labelled with its count and its is_word. Insert a word
and watch both move. Look up a prefix to land on a node whose is_word is
still F - the distinction section 3 is about, on a trie you built yourself.
Click any stored word to delete it and watch the pruning rule decide how much
of its tail actually goes: delete card and nothing but the final d
disappears, delete dog and all three of its nodes go at once.
Every character sits on an EDGE. Walk a path and read the labels you cross - the node you land on does not know its own name.
5. What a trie costs
Every trie operation - insert, search, prefix check - costs O(L), where L
is the length of the string involved. Not O(log n), not O(n): the number
of other strings already stored never enters the cost at all, because each
step only ever looks at the current node's children dict for the next
character.
Searching a
trie holding three words or three million costs the same O(L) for a word
of length L, because the walk never has a reason to look sideways at any
sibling branch. A hash set matches that for exact lookup, but a trie is the
only structure of the two that can also answer prefix questions in O(L),
without a scan over anything.
| Operation | Hash set of strings | Trie |
|---|---|---|
| Insert one string | O(L) amortized (hash the whole string) | O(L) |
| Exact search | O(L) amortized | O(L) |
| "Does any stored word start with this prefix?" | O(n * L) - check every string | O(L) - one walk |
| List all words with a given prefix | O(n * L) scan | O(L) to find the node, then one DFS over just that subtree |
| Memory | one copy of each string | shared prefixes stored once, but each node has real overhead (a dict, an object) |
That memory line is the honest trade-off: a trie of many short, low-overlap strings can use more memory than a hash set of the same strings, because every branch point is its own node with its own dictionary, and Python object overhead is not free. Tries win when strings share prefixes heavily and when prefix queries are actually asked - not automatically, and not for free.
6. The problems a trie makes easy
Prefix search / autocomplete. Walk the prefix to find its node in O(L),
then DFS the subtree under that node to collect every completion - the trie
does the filtering for you; nothing outside that subtree is ever visited.
Word search on a board (LeetCode 212). Given a grid of letters and a list of target words, a naive DFS-per-word re-scans the whole board once per word. Inserting all target words into one trie first lets a single DFS over the board prune itself: at each cell, only step to a neighbour whose letter is an actual child of the current trie node. The instant a partial path has no matching trie node, that entire branch of the board search dies immediately, rather than continuing to build a string nobody is looking for.
The speedup only exists if the board DFS carries the current trie node
along and stops the moment letter not in node.children. A solution that
still builds the full candidate string at every cell and checks it against
the trie only at the end has paid for the trie's memory without collecting
its actual benefit - the pruning has to happen during the walk, not after
it. The other common version of this bug is not removing a found word's
is_word flag (or a found marker) once reported, which lets the same word
be reported twice if the board contains it via two different paths.
Maximum XOR of two numbers (a binary trie over bits). Fix a bit width and
insert every number as a path of 0/1 edges, most significant bit first.
To maximize x XOR y for a query x, walk the trie greedily: at each level,
XOR is maximized by disagreeing on that bit, so try to step to the child
labelled with x's current bit flipped - and only fall back to the
matching bit if that branch does not exist.
Always fix the bit width up front and walk most-significant-bit first.
Both numbers being compared need to branch at the same positions for "flip
the bit" to mean the same thing on both sides. BITS = 31 covers ordinary
32-bit signed integers with room for the sign bit; get this wrong and two
numbers that should share a long common prefix instead diverge at the wrong
level.
7. Variants worth knowing
| Variant | What changes | When it earns its keep |
|---|---|---|
| Compressed / radix trie | A chain of single-child nodes collapses into one edge labelled with a whole substring, not one character. | Long shared prefixes with few branch points - IP routing tables, file-path tries, anywhere the alphabet-per-node overhead of a plain trie is the bottleneck. |
| Suffix trie | Insert every suffix of one string as its own trie path. | Any-substring queries ("does X contain Y") in O(length of Y), at O(n^2) space for a length-n string - the naive suffix trie is rarely built as-is. |
| Suffix automaton / suffix tree | The same substring queries as a suffix trie, built to use only O(n) states by merging equivalent suffixes. | The production-grade version of the line above - real substring-indexing workloads use one of these, not a raw suffix trie. |
Sorted list + bisect | No tree at all: keep the strings sorted and binary-search for a prefix's range. | The input is static (no inserts after the first build). bisect_left/bisect_right on the prefix find the same range a trie would, in O(log n) comparisons of O(L) each, with far less memory than any trie. |
A static set of strings rarely needs a trie at all. If nothing is ever
inserted after the initial build, sort the list once and use
bisect.bisect_left/bisect_right against prefix and prefix + ''
to carve out the matching range - no nodes, no dictionaries, no per-character
object overhead. Reach for an actual trie when strings are inserted
incrementally, or when the branching structure itself is the thing being
exploited, as in the XOR trie above.
8. Where tries actually show up
Every application below is the same two moves: a prefix is a path, and everything sharing that prefix is one subtree. What changes is what the alphabet is and what you do once you land.
Autocomplete and search suggestions. Type car into a search box and the
suggestion list is the subtree under the node c -> a -> r, collected by the
DFS in section 6. Nothing outside that subtree is ever touched, so the cost
scales with what you show, not with how much is indexed. Production versions
store a popularity score on each node alongside count and keep the best few
completions precomputed there, so the dropdown is a read rather than a search.
Spell check. The naive version compares the typo against every dictionary
word, which is a full scan per keystroke. A trie turns it into one bounded
edit-distance DFS: carry an edit budget down the walk and abandon a branch the
moment the budget is spent. Misspell recieve and the whole a, b, d...
subtree under the root dies after one character, because no correction within
two edits can start there. Branches are discarded in blocks, not words.
IP routing, longest prefix match. A router's forwarding table maps address prefixes to next hops, and the rule is that the longest matching prefix wins. Walk the destination address bit by bit through a binary trie and remember the deepest node that carried a next hop - when the walk stops, that remembered node is the answer, found in one pass with no comparisons against non-matching routes. Real tables use the compressed form from section 7: a routing trie is mostly long runs of single-child nodes, which is exactly the case a radix trie collapses.
T9 predictive text. The alphabet is the keypad, not the letters. Pressing
2 means a, b or c, so each edge is a digit and each node holds every
word consistent with the digits pressed so far. 4663 walks four edges and
lands on a node whose subtree contains good, home, gone and hood -
the ambiguity is resolved by ranking that subtree, not by asking which letter
was meant.
Word games. Boggle and Scrabble solvers are the board search from section 6 wearing a different board. The win is the same: carry the current trie node alongside the path, and the instant the next tile is not a child, that entire direction of the search is abandoned rather than explored to full depth. On a Boggle board this prunes the overwhelming majority of paths, because most letter sequences are not the prefix of any English word.
Lexicographic order, for free. Walk a node's children in sorted key order
and the DFS emits every word beneath it already sorted - no sort step, no
comparison between whole strings. A hash set cannot do this at all, and a
balanced tree pays O(log n) string comparisons per word to do it. This is
why a trie is the natural index behind "the next 20 entries after this one" in
a dictionary or a filesystem listing.
Characters give you autocomplete and spell check. Bits give you longest-prefix routing and the max-XOR trie from section 6. Keypad digits give you T9. Board moves give you Boggle. The structure never changes - only what a single edge means.
Practice
- Build and Search - implementing the
structure itself, and the walk that
searchandstartsWithshare.
Where to go next
- Heaps & Priority Queues - the other tree on this
shelf that is rarely drawn with
TreeNodepointers in real code. - Range Query Trees - segment trees and Fenwick trees, the other family of trees built for one specific query rather than general storage.
- Trees in the Wild - the same what-is-this-actually-for treatment for the rest of the tree family: B+ trees, the DOM, LSM trees, and git's Merkle tree.
- Balanced Trees - the general-purpose
ordered-string alternative to a trie, with
O(log n)operations instead ofO(L)but no prefix-query shortcut.