Trie Fundamentals — Recognition, Template, Three Walkthroughs

A trie is a hash map arranged into a tree. Every path from the root spells a prefix; every leaf spells a word. That single reframe — "keys stored path-wise, not hash-wise" — is what makes autocomplete, prefix counting, wildcard matching, and multi-word grid searches turn from "brute-force scan every word" into "walk one tree once". This post is the pattern-recognition guide: when to reach for it, why the template is fifteen lines, and how it composes with DFS for the hard problems.

Recognition — when to reach for it

Trie is the right tool when all three of these hold:

Your input is a collection of strings (or sequences over a fixed alphabet — bit strings, DNA sequences).
The questions you ask are about prefixes — starts-with, all-words-under-this-prefix, longest common prefix, wildcard matching.
A hash map alone would need to touch every stored word to answer, giving O(N × L) per query. The trie answers most queries in O(L) instead.

Canonical use cases:

Autocomplete / prefix search. LC 208 Implement Trie, LC 211 Design Add and Search Words.
Multi-word search over one text. Aho-Corasick territory, but the trie is the substrate. LC 212 Word Search II uses a trie to search a grid for all words in a dictionary in one DFS.
Longest common prefix. LC 14 (though a plain scan beats trie construction for small inputs).
Encoded-key lookups. IP-address routing tables ("longest prefix match") are tries at heart.

Mental model — a tree where the paths are the words

A trie node contains:

A map from a character to a child node. Usually a dict / hash map (children: dict[str, TrieNode]) or a fixed-size array of 26 entries for lowercase-English inputs.
A boolean flag marking whether the path from the root to this node spells a complete word. Sometimes replaced by "count of words ending here" for repeat-word support.

To insert "cat", start at the root: walk to (or create) child c, then a, then t, then set is_word = True at the final node. To search: walk the same characters; if you can't find a child or you land at a node without is_word, the word isn't there.

Space: O(total characters across all inserted words) — up to O(N × L) worst case, but much less when words share prefixes (which is exactly when the trie's read speed pays off).

Time per operation, insert or search: O(L) where L is the length of the input word — independent of how many other words are in the trie. This is the killer property.

The template

class TrieNode:
    __slots__ = ("children", "is_word", "word")

    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_word: bool = False
        self.word: str | None = None       # only populated for word-lookup use cases (LC 212)


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_word

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None

    def _walk(self, s: str) -> TrieNode | None:
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Twenty-five lines including the class scaffolding, and it handles insertion, exact search, and prefix search. _walk is the shared primitive — every op is "walk to the end of a string; if we ran out of children, fail; otherwise inspect the terminal node."

Use __slots__ on TrieNode for a real memory win when the trie holds tens of thousands of nodes — Python instance dicts add significant overhead per node.

Two representations of `children`

dict[str, TrieNode]. Flexible — supports any alphabet including Unicode. Slightly more memory per node.
list[TrieNode | None] of length 26 (or the alphabet size). Faster lookup constant factor for lowercase English; wasted memory for sparse tries. Use ord(ch) - ord('a') as the index.

For interview code, the dict form is idiomatic Python and reads well. Bring up the array form as an optimisation aside if the interviewer asks about the alphabet.

Walkthrough 1 — LeetCode 208, Implement Trie (Prefix Tree)

Implement insert, search, and startsWith on a trie.

The template above is the solution to LC 208 — literally paste it, replace the return type imports, and you're done. That's why LC 208 is the friendliest trie problem and the natural first walkthrough.

Complexity for all three ops: O(L) time (walk the input), O(L) space per new insert (worst case, one new node per character).

Walkthrough 2 — LeetCode 211, Design Add and Search Words Data Structure

addWord(word) inserts a word. search(word) supports the wildcard . — a single-character match.

The insert is unchanged. The search now branches: on a . character, we have to try every child at the current node. That turns exact-match's linear walk into a bounded DFS.

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def search(self, word: str) -> bool:
        def dfs(i: int, node: TrieNode) -> bool:
            if i == len(word):
                return node.is_word
            ch = word[i]
            if ch == '.':
                return any(dfs(i + 1, child) for child in node.children.values())
            if ch not in node.children:
                return False
            return dfs(i + 1, node.children[ch])

        return dfs(0, self.root)

Worst-case time complexity: O(26^d) where d is the number of . characters in the query, because each dot forks into up to 26 branches. In practice, sparse tries prune most branches immediately. For queries with no dots, this reverts to O(L).

The pattern-recognition insight: exact match walks one path; wildcards fork the walk into a DFS. Every trie problem with any kind of pattern matching is this shape.

Walkthrough 3 — LeetCode 212, Word Search II

Given an m × n grid of letters and a dictionary of words, return all words that can be formed by adjacent (up/down/left/right) letters. Cells can't repeat within a word.

The naïve solution runs LC 79 (Word Search) once per dictionary word: O(N × m × n × 4^L). For a big dictionary that's brutal.

The trie insight: build a trie from the dictionary once, then DFS the grid once, walking down the trie in lockstep with the grid. Every path in the grid that matches a trie path is a candidate; every trie leaf we reach spells a found word.

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    # Build the trie
    root = TrieNode()
    for word in words:
        node = root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True
        node.word = word    # remember the whole word at the leaf

    rows, cols = len(board), len(board[0])
    found = set()

    def dfs(r: int, c: int, node: TrieNode) -> None:
        ch = board[r][c]
        if ch not in node.children:
            return
        nxt = node.children[ch]
        if nxt.is_word:
            found.add(nxt.word)
            nxt.is_word = False   # dedup: don't re-emit

        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          # undo

        # Optional pruning: prune empty trie branches to speed up future DFS
        if not nxt.children:
            del node.children[ch]

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)

    return list(found)

Two composition ideas earning their keep:

Trie + DFS + backtracking. Grid DFS with mark-visited-in-place (from BFS vs DFS and the backtracking template), combined with a trie walk to prune the search space. Each cell in the grid is only visited if there's some word starting with the letters seen so far.
Prune empty trie branches on the way back up. Once a subtree of the trie is exhausted (no words left), we can delete the edge that led to it. This turns "worst case is n × m × 4^L" into "worst case is n × m × 4^L, but average case shrinks dramatically as words get consumed."

The trie's O(L) walk turns "search each of N words separately" into "walk the grid once, checking every path against every word in parallel". That's the technique's headline win.

Common bugs

Missing is_word check on exact search. "cat" inserts nodes for c, a, t. If you search for "ca", the walk succeeds but is_word is False at node a (unless "ca" was also inserted). Returning True because the walk didn't fail is a classic wrong answer.
Mixing startsWith and search. startsWith returns True if the prefix walks; search requires the final node to have is_word == True. Interviewers love catching this.
Forgetting to undo the visited mark in LC 212. The backtracking undo restores the original character. Without it, the next DFS from a sibling cell sees '#' and short-circuits — quietly wrong output.
Storing children as defaultdict(TrieNode) and using in to test membership. defaultdict.__contains__ doesn't trigger the factory, but dict[key] does. Testing with in is fine, but a naïve node = children[ch] inserts an empty child on miss. Use plain dict and check with in explicitly.
26-letter array assumption on Unicode input. Blows up if the input contains any non-ASCII character. Stick with dict-of-string for anything not guaranteed to be lowercase English.

When trie is not the tool

Single-word queries with no prefix aspect. A hash set gives O(1) membership; the trie's O(L) is worse.
The alphabet is enormous. Unicode's full BMP is ~65k characters; a 65k-child array per node is unusable. Dict form works but the constant factor makes hash-map approaches competitive.
Very few words with very long shared prefixes. Compressed tries (radix trees / Patricia tries) merge single-child chains into edge labels, saving space. Worth mentioning if the interviewer asks; rarely worth implementing in an interview.
The problem is fuzzy matching with edit distance. Trie DFS with a per-node edit budget works (LC 1032 Stream of Characters is a related shape), but for general fuzzy match, BK-trees or n-gram indexes are cleaner.

How the Algotrek tutor would prompt you here

When a learner opens a trie problem on Algotrek, the tutor doesn't reveal the template. It asks three questions:

"Is the question about prefixes, or just about whole-word membership?" — Prefixes point at trie. Whole-word only points at hash set. Naming the axis is what tells you the technique.
"What does 'match' mean at a single character step?" — Exact character → single walk. Wildcard . → DFS over children. Regex-like patterns → recursive walk with pattern-index bookkeeping.
"Are you matching one query against many words, or many queries against one text?" — One query, many words → trie of the words, search the query. Many queries against one text → build the trie once, then reuse across queries. LC 212 is the "many words, one text" case with the trie in the outer loop.

Answer all three and the template scales cleanly. Try the Implement Trie lesson on Algotrek to see the prompt-then-reveal flow on the simplest trie problem, then step up to the Design Add and Search Words lesson for the wildcard-DFS composition.

Where to go next

LC 421, Maximum XOR of Two Numbers in an Array. Binary trie (children 0 and 1) — same structure, different alphabet. A great "trie for bit strings" problem.
LC 1032, Stream of Characters. Reverse-trie for suffix matching on a stream. Composes reverse-inserted trie with a rolling walk.
LC 336, Palindrome Pairs. Trie plus a clever palindrome check. Hard; the natural graduation problem after LC 212.
Suffix trees and suffix arrays. Once you own tries, the next tier of string data structures becomes readable. Interview-adjacent for competitive programming; rarely required in FAANG interviews.

Cross-reference the BFS vs DFS post and the backtracking template — LC 212 composes the trie with both. Cross-reference the hash-map-vs-hash-set post — a trie is what you reach for when the hash set can't answer prefix questions.

For the O(L)-per-op claim and the O(total characters) space bound, see the Big-O cheat sheet.