These are my data structures and algorithms notes, cleaned up into nineteen posts, one pattern at a time. This one covers tries: a rooted tree whose edges are characters, built to answer prefix questions in time proportional to the prefix rather than to the number of stored words.
A hash set is perfect until the question stops being “is this exact word stored?” and becomes “is anything stored that starts with these letters?”. A trie is the structure built for that second question. It spells every stored word out as a path from a shared root, so words with a common prefix share the nodes for that prefix, and any prefix query costs one step per character no matter how many words you stored.
Tries build directly on Trees, and that parent matters: a trie is a rooted tree whose edges are characters, so everything from Part 8 about walking down a tree and recursing over children carries straight over. It sits beside Heap / Priority Queue and Backtracking as the three topics Trees unlocks, and it is a leaf: nothing later in the series depends on it.
The one prerequisite here is the trie itself, so this post is one foundational module followed by the integration and the problem list.
How to use this post: the method. Checkpoints have no answers on the page: work them out, then open the linked chat to have your answer checked.
Trie
Foundation
Think of a paper dictionary’s thumb tabs. To find “card” you don’t scan every word; you jump to C, then to the CA section, then CAR, and at each step everything that doesn’t start with what you’ve read so far is already out of view. A trie makes that literal. The root stands for the empty string. Each edge adds one character. The node you reach after following the characters of some string s is s, in the sense that it represents exactly one prefix, and everything below it is every stored word that starts with s.
The mental model worth keeping: a trie is the set of all prefixes of all stored words, with each distinct prefix stored once as a node, and each prefix pointing to the prefixes one character longer. A word and a prefix look the same in that structure, so each node also carries a flag or counter saying “a stored word ends exactly here”.
What it solves: prefix questions (does any word start with p, how many do, list them) in O(length of p) instead of O(number of words), and shared-prefix walks where many words are matched against the same input one character at a time, so work done for a common prefix is done once.
Mechanics
To keep the list problems untouched, I’ll teach the trie through an API none of them uses: a word counter that supports
- insert(word), duplicates allowed,
- count_words(word), how many times exactly this word was inserted,
- count_prefix(prefix), how many inserted words start with prefix,
- completions(prefix), every inserted word that starts with prefix, in sorted order.
Each node holds three things: a dict children mapping one character to the next node, pass_count (how many inserted words run through this node), and end_count (how many inserted words end exactly here).
Worked example. Insert, in this order: cat, car, card, care, dog. That is 5 words and 3 + 3 + 4 + 4 + 3 = 17 characters.
Insert walks down, creating only what is missing. Start at the root. For each character, if the current node has no child for it, create one; then step into the child and add 1 to its pass_count. After the last character, add 1 to that node’s end_count. Running it on the example:
- cat: c new, a new, t new. The trie now has 4 nodes (root plus 3).
- car: c reused, a reused, r new. 5 nodes.
- card: c, a, r reused, d new. 6 nodes.
- care: c, a, r reused, e new. 7 nodes.
- dog: d new, o new, g new. 10 nodes.
17 characters went in and only 9 non-root nodes came out, because “ca” was shared by four words and “car” by three. Why is reusing a node safe? Because a node represents one prefix and nothing else. The node reached by c then a is the “ca” node regardless of which word led you there, so cat and card both belong under it. Creating a second “ca” node would split the words that start with “ca” across two places and every prefix count would be wrong.
Why the root gets counted too. Insert also adds 1 to root.pass_count. Every word starts with the empty prefix, so root.pass_count is the total number of words (5 here), which makes count_prefix(“”) correct without a special case.
A lookup is a walk that may fall off. count_words and count_prefix share one helper: walk from the root following the query’s characters, and return the node you land on, or None the moment a character has no child. The walk for “car” visits c (pass 4, end 0), a (pass 4, end 0), r (pass 3, end 1). So count_prefix(“car”) = 3 (car, card, care) and count_words(“car”) = 1. The walk for “cab” visits c and a, then finds no b child and returns None, so both counts are 0.
Why is stopping at the first missing character safe? If no child exists for b under “ca”, then no inserted word ever had “cab” as a prefix, because insert would have created that exact node. There is nothing further down to find.
The key invariant. After any sequence of inserts: the node for prefix p exists if and only if some inserted word starts with p; its pass_count equals the number of inserted words (with multiplicity) that start with p; its end_count equals the number of inserted words equal to p. Every operation above is just reading that invariant off the right node.
The word/prefix distinction. The “ca” node exists and has pass_count 4, yet count_words(“ca”) is 0 because its end_count is 0. Existence of a node means “some word starts like this”, never “this is a word”. That is the most common trie bug I know of, and the reason end_count (or an is_end flag) exists.
Enumerating completions is a DFS below the walk. Walk to the prefix node first. From there, run a depth-first traversal over children, keeping the characters of the current path in a list: append a character before recursing into a child, pop it after. Whenever the node you are on has end_count > 0, the current path is a stored word. For “ca”, visiting children in sorted order gives car, card, care, cat. This is the Trees-post DFS, with one difference: a trie node can have up to one child per alphabet letter instead of two.
Diagram
The trie after all five inserts, each node labelled with the prefix it represents and its two counters. Edges carry the character that extends the prefix.
The two lookups from Mechanics, as walks. Each box is the node reached after consuming that character.
Implementation
class TrieNode:
__slots__ = ("children", "pass_count", "end_count")
def __init__(self):
self.children = {} # char -> TrieNode, only for characters that actually occur
self.pass_count = 0 # number of inserted words whose prefix path runs through this node
self.end_count = 0 # number of inserted words that end exactly at this node
class WordCounter:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
# Every word has the empty prefix, so root.pass_count ends up equal to the
# total number of inserts (5 after cat, car, card, care, dog).
node.pass_count += 1
for ch in word:
if ch not in node.children:
# No inserted word has had this prefix yet, so create its node.
# Example: inserting "card" creates only the d node; c, a, r already exist.
node.children[ch] = TrieNode()
node = node.children[ch]
node.pass_count += 1
# node is now the node for the full word; count it as a word, not only a prefix.
node.end_count += 1
def _walk(self, prefix):
"""Return the node for prefix, or None if no inserted word starts with prefix."""
node = self.root
for ch in prefix:
node = node.children.get(ch) # .get never creates a node, so lookups can't grow the trie
if node is None:
# Example: for "cab", the "ca" node has children {'t', 'r'} and no 'b',
# so no inserted word starts with "cab" and nothing deeper can exist.
return None
return node
def count_words(self, word):
node = self._walk(word)
# A node that exists but has end_count 0 is only a prefix: "ca" -> 0.
return 0 if node is None else node.end_count
def count_prefix(self, prefix):
node = self._walk(prefix)
# pass_count was maintained during insert, so this is O(len(prefix)) with no subtree scan:
# "car" -> 3 (car, card, care), "" -> 5, "x" -> 0.
return 0 if node is None else node.pass_count
def completions(self, prefix):
start = self._walk(prefix)
if start is None:
return []
out = []
path = list(prefix) # characters of the prefix the current node represents
def dfs(node):
if node.end_count:
# Repeat the word once per insert so duplicates are reported, e.g. "a" inserted twice.
out.extend(["".join(path)] * node.end_count)
# sorted() gives lexicographic output; plain dict order would follow first insertion,
# which yields cat before car for prefix "ca" in this example.
for ch in sorted(node.children):
path.append(ch) # path now spells the child's prefix
dfs(node.children[ch])
path.pop() # restore path to this node's prefix before the next child
dfs(start)
return out
wc = WordCounter()
for w in ["cat", "car", "card", "care", "dog"]:
wc.insert(w)
print(wc.count_words("car"), wc.count_words("ca"), wc.count_words("cars")) # 1 0 0
print(wc.count_prefix("car"), wc.count_prefix("ca"), wc.count_prefix("")) # 3 4 5
print(wc.completions("car")) # ['car', 'card', 'care']
print(wc.completions("ca")) # ['car', 'card', 'care', 'cat']
print(wc.completions("z")) # []
I ran this on the worked example and the printed values are the ones in the comments. Edge cases checked the same way: an empty WordCounter gives count_prefix(“”) = 0 and completions(“”) = []; after inserting “”, “a”, “a”, count_words(“”) = 1, count_words(“a”) = 2, count_prefix(“”) = 3, and completions(“”) = [’’, ‘a’, ‘a’].
Two claims in there are recalled rather than derived. dict.get returns None for a missing key without inserting it, and Python dicts iterate in insertion order (guaranteed since 3.7); I confirmed the second one on this example, where iterating the “ca” node’s children without sorted() gives cat, car, card, care.
Complexity. Let L be the length of the word or prefix passed in, S the total number of characters inserted across all words, K the number of nodes in the subtree under the prefix node, and σ the alphabet size.
- insert, count_words, count_prefix: O(L) time. Each character is one dict lookup, which is O(1) on average (recalled: Python dict average case).
- completions: O(L + K·σ log σ + T), where T is the total length of the returned words. The σ log σ is the per-node sort; for lowercase letters σ = 26 is a constant, so this is effectively O(L + K + T).
- Space: at most S + 1 nodes, one per inserted character plus the root. Sharing makes it smaller in practice: 17 characters here, 10 nodes. If you use a fixed 26-slot array per node instead of a dict, multiply that by σ.
Recognition
Signals that a trie is in play:
- Prefix questions. “starts with”, “autocomplete”, “all words beginning with”, “is any stored word a prefix of this”, “longest common prefix of a set”.
- Many words against one input, character by character. A dictionary of words and a single text, board or stream that you scan one character at a time. The trie lets that scan abandon a path the moment the characters so far are not a prefix of any word, and it shares that work across every word with the same prefix.
- Queries that are not exact matches. When a query character can match more than one stored character, a hash set forces you to enumerate candidate strings; a trie lets you branch only into children that actually exist.
- A design problem with insert plus some form of search over strings, especially when the constraints give a small alphabet (often lowercase a-z) and short words.
In this topic’s list: Implement Trie Prefix Tree names the structure outright and has the prefix-query signal. Design Add And Search Words Data Structure has the “stored words, queries that are not plain exact matches” signal. Word Search II has the “many words against one input” signal, the input being a grid of letters.
When not to use it:
- Exact membership only. If every query is “is this whole string stored?”, a set does it in O(L) expected time with far less memory and code.
- One-off prefix queries on a static list. Sort the words once; all words with prefix p form a contiguous block you can find by binary search, with no tree to build.
- Non-string keys with range questions (numbers, dates). That is a sorted structure’s job, not a trie’s.
Distinguishing it from its neighbours: a hash set of all prefixes can answer “is p a prefix?” in O(len(p)), but it stores each prefix as a separate string (23 characters for the 9 distinct prefixes in the example, against 9 trie nodes) and cannot enumerate completions. A sorted list plus binary search handles prefix ranges on static data but gets slow for frequent inserts. The trie is the one that stays O(L) for insert and prefix queries while also letting you walk into the matching words.
Pitfalls
- Treating node existence as “word exists”. “ca” is a node in the example but not a word. Every word query has to check end_count (or an is_end flag) on the landing node.
- Creating nodes during lookup. A common shortcut is a trie of nested defaultdict objects. Then a lookup written as node = node[ch] silently creates nodes. I built “cat” and “car” that way (5 nodes including the root), looked up “cow”, and the trie grew to 7 nodes. Use .get or an explicit
incheck in every read path. - Forgetting the root in counting. If insert does not increment root.pass_count, count_prefix(“”) is 0 instead of the number of words.
- Duplicates. A boolean end flag loses multiplicity: insert “a” twice and a flag still says one “a”. Decide whether the problem needs counts.
- The empty string. Inserting “” should mark the root as a word end. The loop body never runs, which is correct, but only if end_count is updated after the loop rather than inside it.
- Shared child objects. With a list of 26 slots, writing [TrieNode()] * 26 makes all 26 slots the same node (recalled: list multiplication copies references). Initialize with None and create nodes on demand.
- Complexity slips. Computing a prefix count by DFS instead of a stored pass_count costs O(L + K) rather than O(L); under “c” that is a walk over 6 nodes instead of reading one integer. Also, recursing once per character is fine for short words, but recursive DFS on words thousands of characters long can hit Python’s default recursion limit (recalled: about 1000 frames).
Active Recall
-
Starting from the five-word trie in the example, you insert “cart”. How many new nodes are created, and what are the “car” node’s pass_count and end_count afterwards?
-
count_prefix(“car”) returns 3 but count_words(“car”) returns 1. Using only the invariant, explain why both answers come from the same node, and what a node with pass_count 4 and end_count 0 (like “ca”) tells you.
-
Why is it safe for a lookup to return “not found” at the first missing child, without looking anywhere else in the trie?
-
A friend suggests replacing the trie with a hash set holding every non-empty prefix of every word. For the five example words, how many entries would that set have, and what can the trie do that the set cannot?
-
completions(“ca”) returned car, card, care, cat. If you removed sorted() from the DFS, what would it return for this insertion order, and why?
Answer out loud or on paper first.
Mini-task
Skipped: Design Add And Search Words Data Structure and Word Search II never mention a trie, so both already make you decide to build one and extend its walk yourself; that independent use belongs in their own sessions.
Transfer test
You’re given up to 10,000 phone numbers, each up to 10 digits. The list is “consistent” if no number is a prefix of another number, because dialling the shorter one would connect before you finished the longer one. For example, 911 and 91125426 make a list inconsistent. You need to answer consistent or not. Would you use a trie? Why?
Integration
There is one prerequisite, and it is the topic, so the connection is direct: every problem in this list is the trie from the module plus one extra layer. What changes from problem to problem is who drives the walk.
- The query drives the walk, one path. This is exactly what the module built: follow the characters of a string from the root, land on a node or fall off, read the node’s flags. Insert, word lookup and prefix lookup are all this shape.
- The query drives the walk, but some steps branch. When a query character is allowed to match more than one child, the single walk becomes a DFS over the children that exist, the same recursion completions uses below its prefix node. The trie’s value is that it only lets you branch into children that are actually present.
- Something outside the trie drives the walk. When the characters come from some other search (a traversal of another structure, a scan through a text), the trie becomes an oracle that search consults at each step: “is the string so far still a prefix of some word, and is it a word?”. The early exit from Active Recall question 3 becomes pruning for that outer search. This is where the trie meets the DFS from Trees and the choose/explore/un-choose loop that Backtracking formalizes (the append and pop around the recursive call in completions is the same move).
Distinguishing competing approaches:
| Situation | Reach for | Why |
|---|---|---|
| Exact membership only | Hash set | O(L) expected, less memory, no tree |
| Prefix queries on data that never changes | Sorted list + binary search | Words with a common prefix are contiguous after sorting |
| Inserts mixed with prefix queries, or listing completions | Trie | O(L) insert and prefix walk, and links to every extension |
| Query characters that can match several stored characters | Trie with DFS over existing children | Branches only where stored words actually differ |
| Many words searched for inside one input at the same time | Trie of the words, walked by the outer search | Shared prefixes are checked once; dead prefixes stop the search early |
A recognition checklist for an unfamiliar problem:
- Is the data a collection of strings (or digit or bit sequences) over a small alphabet?
- Does any question mention prefixes, starts-with, autocomplete, or “is one of these a prefix of another”?
- Are many words matched against the same input, character by character, where an exact-match set would force you to check each word separately?
- Can a query character match more than one thing?
- Do inserts and queries interleave, so sorting once doesn’t cover it?
- If only 1 is true and every query is an exact match, use a set. If 2 is true on static data, consider sort and binary search first. If 3, 4 or 5 is true alongside 1, build a trie, and decide what each node needs to store (an end flag, counts, something else) by asking what the query has to read when it lands.
The problems
Work these with the solving cycle from the method: a 15-minute honest struggle, one key sentence per problem once it clicks, then spaced repetition. For tries, the struggle questions are the tree ones: can I combine results from the children of a node? Reconstruct the call stack on a small example of three or four words, and explain how information flows between the leaves and the root (what the walk reads on the way down, what a DFS reports on the way back up).
3 problems · 0 easy · 2 medium · 1 hard · tracker spreadsheet (.xlsx)
| # | Problem | Difficulty | Coach |
|---|---|---|---|
| 1 | Implement Trie Prefix Tree | Medium | ChatGPT · Claude |
| 2 | Design Add And Search Words Data Structure | Medium | ChatGPT · Claude |
| 3 | Word Search II | Hard | ChatGPT · Claude |
Take this lesson as a live session
If you would rather be taught this interactively, with the coach waiting for your answers, open the whole lesson as a prompt in a chat.