Trie

TL;DR

A trie is a tree where each node holds a dictionary children: {char → node} and a boolean is_end flag. Inserting "apple" walks the tree one character at a time, creating nodes for any character that doesn’t already exist, and flips is_end = True on the final node. Searching for a word does the same walk and returns true only if the walk completes and the terminal node has is_end = True. Searching for a prefix is identical but skips the is_end check.

The whole point: insert, search, and startsWith are all O(L) where L is the length of the query word. The size of the dictionary doesn’t matter. A trie holding 10 words and a trie holding 10 million words both answer search("apple") in 5 hops.

The cost shows up in space, not time. Each character in each word may need its own node, so worst-case space is O(total characters across all words). Shared prefixes reclaim some of that — "app", "apple", "apricot" share their first two nodes — which is the structural win that makes the trie pay for itself on dictionary-heavy workloads.

When to reach for it

Signals that a trie is the right move:

• Autocomplete / type-ahead. Given a prefix, return all words that extend it. Hash maps can’t do this; a trie walks to the prefix node in O(L) and then DFS-collects everything below.
• Prefix-based dictionary problems. “Replace every word in a sentence with its shortest root from a dictionary” (LC 648), “find the longest common prefix of n strings”, “given a stream of words, count how many share each prefix”.
• Word search on a 2D board (LC 212). Multiple target words, one shared board. The trie lets a single DFS prune branches that can’t possibly match any remaining word.
• Wildcard / pattern search. A '.' matches any character (LC 211); the trie structure naturally supports a DFS fork over all children when the query character is a wildcard.

If your workload is “given an exact key, return its value” with no prefix or pattern semantics, use a hash map — it’s faster in practice and lighter on memory.

Flavor 1 — implement Trie (LC 208)

The canonical implementation. A TrieNode is a children dict plus an is_end flag; the Trie is just a wrapper around the root.

class TrieNode:
    __slots__ = ("children", "is_end")

    def __init__(self) -> None:
        self.children: dict[str, "TrieNode"] = {}
        self.is_end: bool = False


class Trie:
    def __init__(self) -> None:
        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_end = True

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

    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:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

Worked example. Insert ["app", "apple", "apricot"] in order, then run three queries.

After all three inserts, the tree looks like:

(root)
 └── a
     └── p
         ├── p ●        ← is_end (from "app")
         │   └── l
         │       └── e ●   ← is_end (from "apple")
         └── r
             └── i
                 └── c
                     └── o
                         └── t ●   ← is_end (from "apricot")

Node-by-node:

Now trace each query:

The search("ap") case is the whole reason is_end exists: the path exists in the trie because "app", "apple", and "apricot" all need it, but "ap" was never inserted as a word, so the flag is false.

Flavor 2 — wildcard search (LC 211)

addWord is identical to insert above. search allows '.' to match any character, which forces a DFS fork at every dot.

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

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word: str) -> bool:
        def dfs(i: int, node: TrieNode) -> bool:
            if i == len(word):
                return node.is_end
            ch = word[i]
            if ch == ".":
                return any(dfs(i + 1, child) for child in node.children.values())
            nxt = node.children.get(ch)
            return nxt is not None and dfs(i + 1, nxt)

        return dfs(0, self.root)

Short trace. Dictionary ["bad", "dad", "mad"], query search(".ad"). At i=0 the character is '.', so we DFS into all three root children (b, d, m). Each branch then matches 'a' and 'd' exactly and arrives at an is_end = true node. The first branch to succeed short- circuits via any. Without the trie, you’d be running three substring checks; with it, the shared 'a' → 'd' tail would coalesce if the words shared more structure.

Flavor 3 — Word Search II (LC 212)

You’re given an m × n board of letters and a list of words. Return every word that can be assembled by walking 4-connected neighbours without reusing a cell. The naive solution runs the standard board-DFS once per word: O(W × m × n × 4^L) where W = len(words) and L is max word length. For W = 10⁴ words on a 12 × 12 board, that’s hopeless.

The trie fix: insert every target word into a trie, then run one DFS from each board cell, advancing a trie pointer in lockstep with the path.

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.word = w  # stash the full word at the terminal node

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

    def dfs(r: int, c: int, node: TrieNode) -> None:
        ch = board[r][c]
        nxt = node.children.get(ch)
        if nxt is None:
            return                            # prune: no word uses this prefix
        if getattr(nxt, "word", None):
            found.add(nxt.word)
            nxt.word = None                   # de-dupe hits
        board[r][c] = "#"                     # mark visited
        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

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

Why it’s tractable: the DFS bails the instant node.children.get(ch) is None. If no word in the dictionary starts with the prefix you’ve walked on the board, the entire subtree is dead. With W = 10⁴ words sharing a few hundred prefixes, you walk the board roughly once — not 10⁴ times.

Why it works — the invariant

Every trie operation walks a path from root to depth L. Every node on that path is shared by every word that has the same prefix up to that depth. So the cost of looking up a word depends on how long the word is, not on how many words exist. That’s the entire structural argument.

The corollary for board search: pruning a single trie edge eliminates every word in the dictionary that started with that prefix in one stroke.

Complexity

Total trie space is O(Σ Lᵢ) across all inserted words, worst case (no shared prefixes). With heavy prefix sharing — English dictionaries, URL paths, IP prefixes — actual node count is much lower than the bound.

Common pitfalls

• Forgetting is_end. Without it, search("ap") returns true after inserting "apple" because the path exists. The flag is what distinguishes “this is a word” from “this is a prefix of a word”.
• Fixed-size array [None] * 26 for non-ASCII. Fine for lowercase English, blows up the moment you hit Unicode, mixed case, digits, or symbols. Use a dict unless you’ve measured a hot path that needs the array’s cache locality.
• Naive delete leaves orphan branches. Just flipping is_end = False is correct but wastes memory; properly removing a word means walking back up and dropping nodes that have no other children and aren’t themselves ends. Get this wrong and a long-lived trie leaks.
• Memory blowup. Storing 10⁶ random strings in a vanilla trie is expensive — every node is a Python object plus a dict. Mitigations: a radix tree (compress chains of single-child nodes into one edge labelled with a substring), or a DAWG (collapse identical suffix subtrees so the structure becomes a DAG, not a tree).
• Mutating the board without restoring it in Word Search II. Forget the board[r][c] = ch restore line and the next DFS sees '#'s everywhere.

Where you see this in production

• Linux kernel routing tables. net/ipv4/fib_trie.c stores the IPv4 forwarding table as a level-compressed trie (LC-trie / Patricia variant) on the IP prefix bits — longest-prefix match is the routing decision, and a trie is the only structure that does it in O(prefix length).
• DPDK packet classification. librte_lpm (Longest Prefix Match) is a multibit trie used by userspace network functions to classify millions of packets per second per core.
• Elasticsearch completion suggester. The completion field type builds an in-memory FST (finite-state transducer — a compressed, minimised trie) per shard so autocomplete queries return in microseconds regardless of corpus size.
• Language servers / code completion. clangd, rust-analyzer, and gopls index symbol names into trie-like structures so that typing Str in your editor returns String, StringBuilder, Stream etc. without scanning every symbol.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.