L45 · Tries — Prefix Trees

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

Why this session exists

Any problem about prefixes or about a dictionary of words wants a trie. That is nearly the whole recognition rule, and it is unusually crisp for a data structure.

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. The number of words stops multiplying your work and starts constraining it.

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 — I use "#" or the empty string — 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 is what buys you the compression; the prefix query is what a hash set cannot answer.

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 in an interview unless asked otherwise:

END = "#"
 
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 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 hash set cannot do this at all; a trie handles it by branching into all children at the wildcard position.
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 an m × n board of characters and a list of words, return all words that can be formed by a path of adjacent cells, where no cell is reused within a single word.

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 the entire optimisation. Whole regions of the board become unreachable after two characters.
• 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.

END = "#"
 
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 deserve attention because they are what separate an accepted solution from a timeout.

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) when nxt is empty is the real accelerator. Once a trie branch has yielded all its words, it is a dead subtree. Deleting it means future DFS calls never descend into it again. On adversarial inputs — thousands of words sharing long prefixes — this changes the runtime by an order of magnitude. It also mutates the trie, which is fine here because we built it ourselves and will not reuse it.

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. If you use "end" as the marker and a word contains those letters, the paths interfere. Use a character outside the input alphabet — "#" for lowercase-only inputs — or a non-string key like True, which cannot collide with any character key.

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.

Building a fresh trie inside a loop. If the problem calls your function repeatedly, building the trie each time throws away the entire advantage. Build once, query many.

Recursion depth on long words. A word of length 500 means 500 stack frames. Python's default limit is 1000, so this is usually survivable, but check the constraints before assuming.

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: O(m · n · 4^L) in the absolute worst case where L is the longest word, but that bound is wildly pessimistic in practice. The trie prunes almost immediately: a cell whose character is not a child of the root is rejected in O(1), and branch deletion removes exhausted subtrees permanently. The realistic cost is governed by the trie's shape rather than by the theoretical bound.

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.

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.