Tries — Prefix Trees

Review boundary and corrected contracts

A trie terminal must not collide with character keys. The dictionary Trie now uses a private object sentinel; board search assumes lowercase letters and reserves its visit marker. Destructive trie pruning is local to the call, and the input board must be restored.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Build a trie from a plain dict in under ten lines, then use it to turn Word Search II from an impossible search into a routine one.

Series: LeetCode — From Basics to Production-Ready · Session 45 / 65 · Phase 3 · Advanced & specialised

Why this session exists

Repeated prefix queries or an incremental search over a dictionary are strong reasons to consider a trie. Whole-word membership alone often needs only a hash set; one longest-common-prefix query can be answered by directly scanning the strings.

The reason a trie earns its place is that it inverts the direction of the search. Without one, "does this string I am building match any of ten thousand words" forces you to check the string against every word, or at best against a hash set that only answers about complete strings and tells you nothing about partial ones. With a trie you carry a single node pointer alongside your partial string, and that pointer answers two questions in O(1): is this a complete word, and is there any word at all that continues from here. That second question is the one that matters, because it lets you abandon a search branch the instant it becomes hopeless.

Word Search II is the canonical demonstration. Search a grid for each of n words independently and you do n separate backtracking searches, each exponential in path length. Build a trie of all the words and do one search, walking the grid and the trie in lockstep, abandoning any cell whose character is not a child of the current trie node. Shared prefixes avoid repeating equivalent prefix work across words, but trie construction still reads all input characters and board paths can remain exponential.

The other reason to spend a session here is that people over-engineer tries. A TrieNode class with __init__, an array of 26 slots, and a parent pointer is a lot of code to write under pressure. A nested dictionary does the same job in three lines and is faster to get right. I will show both and tell you which to reach for.

Blank-file warm-up

Five minutes, empty file, no notes. Write the insert loop using nested dicts:

1. node = node.setdefault(c, {}) for each character.
2. Mark the end of a word.
3. The search loop, and how it distinguishes "word present" from "prefix present".

The step people forget is the terminal marker. Without it, a trie containing "apple" will report "app" as a stored word, because the path exists. Choose a sentinel key that cannot collide with a character — the code below uses a shared END = object() sentinel (an empty string also cannot equal a one-character edge key) — and set it at the final node.

Pattern anatomy

The shape that summons this pattern: many strings sharing prefixes, and a query about prefixes rather than about whole strings. The sharing compresses repeated prefixes; a plain whole-word hash set lacks a direct prefix query, while a separately built prefix set can provide one.

The invariant: each node represents exactly one prefix — the concatenation of the edge labels from the root to that node. The root is the empty prefix. A node's children are the characters that legally extend that prefix within the stored dictionary. A terminal flag on a node says the prefix is itself a complete stored word.

The dictionary form, which is what I write under a tight review unless asked otherwise:

END = object()
 
def build(words):
    root = {}
    for w in words:
        node = root
        for c in w:
            node = node.setdefault(c, {})
        node[END] = w            # store the word itself, not just True
    return root
 
def search(root, word):
    node = root
    for c in word:
        if c not in node:
            return False
        node = node[c]
    return END in node           # complete word, not merely a prefix
 
def starts_with(root, prefix):
    node = root
    for c in prefix:
        if c not in node:
            return False
        node = node[c]
    return True                  # any node reached means the prefix exists

Storing the full word at the terminal rather than True is a small choice that pays off constantly. In Word Search II it means you can append the found word directly without reconstructing it from the path, and in autocomplete-style problems it saves carrying a separate string.

The class form, for when the problem says "design" and expects an object:

class Trie:
    def __init__(self):
        self.root = {}
 
    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            node = node.setdefault(c, {})
        node[END] = True
 
    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and END in node
 
    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None
 
    def _walk(self, s):
        node = self.root
        for c in s:
            if c not in node:
                return None
            node = node[c]
        return node

The 26-slot form uses ord(c) - ord("a") indexing and reserves space for every possible child. A dict allocates only present edges but has hashing and per-object overhead. Neither representation is universally faster or smaller: alphabet density, implementation and workload decide. A Trie class can also use dictionaries, as the example does.

The cue

You are looking at a trie problem when the statement contains these tells:

1. The word "prefix" anywhere. Starts-with queries, autocomplete, longest common prefix, replace-with-root. This is close to a keyword match.
2. A list of words given as input, queried many times. If you would otherwise loop over the whole word list per query, the trie converts that to a walk proportional to the query length instead.
3. Wildcards inside a search string — a dot matching any character, as in Design Add and Search Words. A plain exact lookup cannot do this directly; a trie branches over character children at the wildcard position, while scanning stored words is another, less selective option.
4. A search that builds a string incrementally and needs early abandonment. Grid search, board games, word ladders. The trie's "does anything continue from here" answer is the pruning signal.
5. Constraints where the total number of characters across all words is bounded — say sum of word lengths <= 10^5. That bound is describing the trie's size, which is a hint that the setter expects you to build one.

Tell 4 is the highest-value one because it is the least obvious. When you find yourself writing a backtracking search that constructs a candidate string, ask whether a trie could tell you to stop earlier.

Guided solve

Word Search II — given a nonempty rectangular m × n board of lowercase letters and nonempty lowercase words, return each matching word once along orthogonally adjacent cells, with no cell reused within one word. The code restores the board on normal completion; it does not promise exception-safe restoration or accept * as an input letter. An empty word list is allowed.

The naive approach is worth stating so you can reject it out loud. For each word, run a DFS from every cell. That is words × m × n × 4^L where L is the word length, and with a few thousand words it is hopeless. The waste is obvious once named: if fifty words start with "ba", you re-walk the same "ba" path fifty times.

The fix is to invert the loop. Instead of iterating words and searching the board for each, iterate board cells once and let the trie tell you which words are still possible.

Build a trie of all words. Then DFS from every cell, carrying two things: the current board position and the current trie node. At each step:

• If the current character is not a child of the current trie node, return immediately. This is prefix pruning. It can reject a path early; how early depends on the dictionary.
• Otherwise descend into that child. If the child has a terminal marker, you have found a word — record it and clear the marker so you do not record it twice.
• Mark the cell as visited, recurse into the four neighbours, then unmark.

# Reuse the END sentinel defined above.
def findWords(board, words):
    root = {}
    for w in words:
        node = root
        for c in w:
            node = node.setdefault(c, {})
        node[END] = w
 
    rows, cols = len(board), len(board[0])
    found = []
 
    def dfs(r, c, node):
        ch = board[r][c]
        nxt = node.get(ch)
        if nxt is None:
            return
        word = nxt.pop(END, None)          # pop: prevents duplicate reporting
        if word:
            found.append(word)
 
        board[r][c] = "*"                  # mark visited in place
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "*":
                dfs(nr, nc, nxt)
        board[r][c] = ch                   # restore
 
        if not nxt:                        # leaf with no remaining words
            node.pop(ch, None)             # prune the dead branch
 
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return found

Two lines beyond the basic algorithm remove duplicate results and avoid revisiting exhausted branches.

nxt.pop(END, None) removes the terminal marker as soon as the word is found. Without this you would need a set to deduplicate, since the same word can often be formed by more than one path. Popping is both the deduplication and a small pruning step.

The trailing node.pop(ch, None) removes a branch only when no terminal or child remains, so it cannot remove an undiscovered word. Future starts then skip that exhausted subtree. The speedup depends on the board and dictionary; no fixed factor or acceptance guarantee follows. Mutation is safe because this trie is private to the call.

Marking visited by overwriting the board cell with "*" and restoring it afterwards avoids a separate visited set. That is a standard grid-backtracking move worth carrying forward.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Implement Trie — insert, search, startsWith. This should be pure transcription after the warm-up. If it is not, redo the warm-up before moving on.
• Replace Words — given a dictionary of roots and a sentence, replace each word by the shortest root that is a prefix of it. Walk the trie and stop at the first terminal you hit; think about why "first" gives you "shortest".
• Design Add and Search Words — the search string may contain dots matching any single character. At a dot you must try every child; think about what that does to the worst-case complexity and whether the constraints permit it.

Common failure modes

No terminal marker, so prefixes report as words. Insert "apple", then search("app") returns True. The fix is one sentinel key, and the test that catches it takes ten seconds.

Sentinel key colliding with a real character. "#" is safe for lowercase-only words but not for arbitrary strings containing #. In contrast, "end" does not collide with one-character keys merely because a word contains those letters. The object sentinel cannot equal a character key. Keep the same END object for insertion and lookup; do not reassign it while stored tries are still in use.

Forgetting to restore the board cell after recursion. Classic backtracking bug. The board stays corrupted and every subsequent search from a different start cell sees garbage. Symptom: the first word is found and nothing after it.

Not deduplicating found words. The same word reachable by two paths gets reported twice. Pop the terminal, or collect into a set.

Reusing a destructively pruned trie. Read-only prefix queries can reuse one trie. This findWords call removes terminals and exhausted branches, so a subsequent independent board search must build a fresh trie or use a separate non-destructive design; rebuilding here is necessary, not a defect.

Recursion depth on long paths. DFS stack depth is bounded by min(longest word length, number of board cells), plus caller frames. Read the current interpreter limit with sys.getrecursionlimit() rather than relying on a universal default or assuming 500 frames are safe. Use an explicit stack for deep inputs.

Myth: A hash set of the words does everything a trie does and is simpler, since lookups are O(1) instead of O(length).

Why: A set containing only complete words does not directly answer prefix membership. A second set of all prefixes can answer it, at the cost of materialising and hashing prefix strings (up to quadratic total prefix characters per long word). A trie shares those prefixes structurally and follows one edge per new character. Hashing a newly built query string takes work proportional to its length; cached hashes and equality checks make repeated lookup costs more nuanced than a universal O(length) claim.

Steps 1: Because words in a dictionary frequently share leading characters, storing each word independently duplicates those shared prefixes once per word.

Steps 2: Because a path from a root through labelled edges uniquely determines the string spelled along it, a tree can represent every shared prefix exactly once.

Steps 3: A node represents a prefix; END marks a complete word and character children represent strict extensions. In this dictionary representation, a terminal entry is not a character child. Walking the next character is an expected O(1) dictionary operation.

Steps 4: Because that check is O(1) and available at every step of an incremental search, a search building a string character by character can abandon a branch the moment no word continues.

Steps 5: Missing trie edges prune impossible prefixes, but the same trie node can be reached along many different board paths. The search is over board position, visited cells and trie node, not one visit per trie node.

Steps 6: Trie construction still costs the total input characters. More words can enable more board paths, so neither sublinear growth with dictionary size nor a 100-to-1000-word speed ratio follows from prefix sharing alone.

Picture: A physical dictionary where you have torn out every repeated prefix. All words starting with 'ca' hang off a single 'ca' tab. Your finger sits on one tab at a time, and moving to the next letter is one step. If there is no tab for the letter you need, you already know no word in the entire dictionary continues that way.

Trigger: Fires when you have a set of words and a search that builds strings one character at a time — grid walks, wildcard matching, autocomplete.

Name: Nested dicts

Gain: Three lines to build; allocates only the children that actually exist; no class boilerplate; handles any alphabet including unicode with no changes

Cost: Per-node Python dict overhead is significant in memory; the sentinel key sits in the same namespace as characters, which needs care

Name: Node class with a 26-slot array

Gain: Predictable memory layout, cache-friendly, and the terminal flag is a genuine separate field with no collision risk; direct indexed access; actual speed depends on density and implementation

Cost: Allocates 26 pointers per node regardless of use, which is wasteful on sparse tries; more code to write correctly under time pressure; hard-codes the lowercase alphabet

Pick: Use nested dicts in Python for any problem where you build the trie inside your solution. Use the array-of-26 node class when writing C++ or Java, or when the problem explicitly asks you to design a Trie class and you want the terminal flag to be an unambiguous field rather than a sentinel key.

Complexity

Insert: O(L) where L is the word length — one dictionary step per character. Building the whole trie: O(total characters) across all words, which is the natural measure and usually what the constraints bound.

Search and startsWith: O(L) in the length of the query, independent of how many words are stored. That independence is the headline property.

Space: O(total characters) in the worst case where no words share prefixes, and substantially less when they do. Each node in the dict form carries Python dictionary overhead, which is real — for very large dictionaries the array form or a compressed trie matters.

Word Search II: build time O(S), where S is total dictionary characters, plus a loose search bound O(m·n·4^D), where D = min(L, m·n) and L is the longest word. No cell can be reused, and later steps have at most three unvisited direction choices, but the search can still be exponential. Auxiliary storage is O(S + D), excluding the returned word references. Prefix pruning and exhausted-branch deletion improve particular inputs without removing that worst case.

Wildcard search with dots: O(26^d · L) where d is the number of dots, since each dot forces branching into every child. Fine for a couple of dots, hopeless for many — check the constraints.

Self-check (answer follows each question).

Q: Why does a trie need a terminal marker rather than treating any leaf as a word?

A: Because a stored word can be a strict prefix of another stored word — 'app' inside 'apple'. Its node is not a leaf, so leaf-ness cannot indicate word-ness. The marker is the only way to distinguish a complete word from a mere prefix.

Q: What does node.setdefault(c, {}) do and why is it the idiomatic insert?

A: It returns the existing child for character c, or creates an empty dict child and returns that. It merges the lookup and the create into one expression, which is exactly what insertion needs at every character.

Q: In Word Search II, what are the two mutations of the trie during the search, and what does each buy?

A: Popping the terminal marker on a found word prevents reporting the same word twice via different paths. Deleting an emptied child node prunes an exhausted subtree so later DFS calls never enter it, which is the main practical speedup.

Q: Why can a hash set not replace a trie for Word Search II?

A: A set of complete words lacks direct prefix queries, but a separate set of prefixes can support them. A trie avoids repeatedly building whole prefix keys and shares their storage, so it is a convenient incremental representation, not the only correct one.

Q: How does a trie handle a wildcard dot in the search string, and what does it cost?

A: At a dot branch over character children only, not END. With an alphabet of size 26 and d dots in a length-L query, a loose bound is O(26^d · L); actual work is limited by existing branches. Terminal checks still happen only at the end of the query.

Q: You need to return the k most frequent completions of a prefix. How would you extend the trie?

A: For a fixed k, maintain a ranked top-k list of word IDs and frequencies at each node on an inserted word's path. Read the prefix node in O(L), then return up to k cached entries. Updates cost extra per ancestor and ties need a rule; a heap alone does not return sorted results in O(k), and frequency decreases or deletions require repairing candidates outside the old top k.

Stretch: true

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Implement Trie should reach cold quickly and stay there. Word Search II will not — it combines three separate skills and deserves a shorter interval than the ladder suggests until you have written it twice unaided.

• Repeated prefix queries are a trie cue; a single prefix computation or whole-word membership may need a simpler method.

• Nested dicts plus a sentinel key is the whole data structure — node = node.setdefault(c, {}) is the entire insert loop.

• Store the word itself at the terminal, not True. You will want it in Word Search II and in every autocomplete variant.

• A trie provides incremental prefix tests and shared storage; a separate prefix hash set is an alternative with different string-allocation costs.

• Word Search II inverts the loop: one grid walk driven by the trie, not one search per word.

• Delete only exhausted trie branches during a private search; this safely avoids repeat work but does not guarantee a particular runtime.

Corrective source notes

• 5. Data Structures — Python 3.14.8 documentation — Dictionaries map unique hashable keys to values; algorithmic state choices require a separate proof. Checked 2026-10-07.

• Python 3.14 dict.setdefault and sys.getrecursionlimit — return/insert behavior and the configurable current interpreter limit. Freshly checked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.