Trie Patterns

A hash set answers “is this exact word present?” in $O(L)$ . It cannot answer “is any word present that starts like this?” without scanning every key. A trie (prefix tree) stores words character by character along shared paths, so prefix questions cost only the length of the prefix — no matter how many words are stored.

The Tries page covers the data structure itself. This page is about recognising when a problem wants one, and the three shapes those problems take.

What you’ll learn

The nested-dictdict trie — 6 lines, and why it beats a TrieNodeTrieNode class in an interview.
Why an end-of-word marker is mandatory, not decorative.
Wildcard search: how one .. turns lookup into a DFS with branching.
Trie-pruned search: the idea that makes LC 212 tractable, and the single most important thing a trie buys you.
Three real LeetCode problems solved in the browser: 208, 648, 211.

The cue

The template — a trie in six lines

You do not need a class. A nested dictionary is faster to write, harder to get wrong, and just as fast in practice.

trie_nested_dict.py

def build_trie(words):
    root = {}
    for word in words:
        node = root
        for ch in word:
            node = node.setdefault(ch, {})   # descend, creating as needed
        node["$"] = True                     # end-of-word marker
    return root
 
 
trie = build_trie(["app", "apple"])
print(trie)
# {'a': {'p': {'p': {'$': True, 'l': {'e': {'$': True}}}}}}

trie_nested_dict.py

def build_trie(words):
    root = {}
    for word in words:
        node = root
        for ch in word:
            node = node.setdefault(ch, {})   # descend, creating as needed
        node["$"] = True                     # end-of-word marker
    return root
 
 
trie = build_trie(["app", "apple"])
print(trie)
# {'a': {'p': {'p': {'$': True, 'l': {'e': {'$': True}}}}}}

setdefault(ch, {})setdefault(ch, {}) is the whole insert: it returns the existing child if there is one, otherwise creates and returns a new empty dict. Searching is the same walk:

trie_search.py

def walk(root, s):
    """Return the node reached by s, or None if the path breaks."""
    node = root
    for ch in s:
        if ch not in node:
            return None
        node = node[ch]
    return node
 
 
def search(root, word):                 # exact word present?
    node = walk(root, word)
    return node is not None and "$" in node
 
 
def starts_with(root, prefix):          # any word with this prefix?
    return walk(root, prefix) is not None

trie_search.py

def walk(root, s):
    """Return the node reached by s, or None if the path breaks."""
    node = root
    for ch in s:
        if ch not in node:
            return None
        node = node[ch]
    return node
 
 
def search(root, word):                 # exact word present?
    node = walk(root, word)
    return node is not None and "$" in node
 
 
def starts_with(root, prefix):          # any word with this prefix?
    return walk(root, prefix) is not None

Complexity, and what a trie actually buys

For nn words of length up to LL, over an alphabet of size |Σ||Σ|:

Operation	Trie	Hash set
Insert	$O(L)$	$O(L)$
Exact search	$O(L)$	$O(L)$ average
Prefix search	$O(L)$	$O(n \cdot L)$ — scan everything
All words with a prefix	$O(L + \text{matches})$	$O(n \cdot L)$
Space	$O(n \cdot L \cdot \\|\Sigma\\|)$ worst case	$O(n \cdot L)$

Exact lookup is not the reason to use a trie — a set matches it and uses less memory. The wins are the two prefix rows, and one more thing that does not fit in a table:

The variant map

Variant	What the trie does	Canonical problem
Basic prefix tree	Insert / search / startsWith	208 Implement Trie
Shortest matching prefix	Walk the word, stop at the first `$$`	648 Replace Words
Wildcard search	On `..`, DFS into every child	211 Design Add and Search Words
Prune a grid DFS	Carry a trie node with the search position	212 Word Search II
Autocomplete / top-k	Walk to the prefix, then collect from the subtree	1268 Search Suggestions
Store a value at each word	Keep a payload beside the `$$` marker	677 Map Sum Pairs
Bitwise trie	Insert 32-bit numbers as paths; greedily take the opposite bit	421 Maximum XOR

Practice — real LeetCode problems

LC 208 — Implement Trie (Prefix Tree) · Medium

Problem. Implement a TrieTrie class with three methods: insert(word)insert(word), search(word)search(word) (is this exact word stored?), and startsWith(prefix)startsWith(prefix) (is any stored word prefixed by this?).

Constraints. 1 <= len(word) <= 20001 <= len(word) <= 2000, lowercase English letters, up to 3 * 10^43 * 10^4 calls total.

Example. Insert "apple""apple"; search("apple")search("apple") is TrueTrue, search("app")search("app") is FalseFalse, startsWith("app")startsWith("app") is TrueTrue; then insert "app""app" and search("app")search("app") becomes TrueTrue.

Editorial — approach, complexity, follow-ups

A trie is a tree whose edges are labelled with characters, so a path from the root spells a prefix. The nested dict represents it directly: each dict maps a character to its child dict.

Time $O(L)$ per operation. Space $O(\text{total characters inserted})$ .

search("appl")search("appl") returning FalseFalse while startsWith("app")startsWith("app") returns TrueTrue is the pair that proves the marker is doing its job. search("")search("") is FalseFalse here because no empty word was inserted — had you called insert("")insert(""), the root itself would carry "$""$" and it would be TrueTrue. Getting that right falls out of the design rather than needing a special case.

Follow-ups you should expect:

“Use a class instead of dicts.” A TrieNodeTrieNode with children: dictchildren: dict and is_word: boolis_word: bool is more readable in production and the natural place to hang extra fields. In an interview, dicts are fewer lines and fewer bugs; say you know both and why you picked one.
“Implement deletedelete.” The interesting part: remove the marker, then prune upward while a node has no children and no marker. Recursion handles it cleanly. Worth practising — it is the follow-up that separates people who understand the structure from people who memorised insert.
“Fixed 26-slot array instead of a dict?” Faster constant factor and predictable layout, but $26 \times$ the memory for sparse tries. Fine for lowercase-only; a dict generalises to any alphabet.
“Count words with a given prefix?” Store a counter at each node, incremented on the way down during insert.

LC 648 — Replace Words · Medium

Problem. Given a dictionarydictionary of root words and a sentencesentence, replace every word in the sentence with the shortest root in the dictionary that is a prefix of it. If no root matches, leave the word unchanged. Return the resulting sentence.

Constraints. 1 <= len(dictionary) <= 10001 <= len(dictionary) <= 1000, 1 <= len(sentence) <= 10^61 <= len(sentence) <= 10^6, lowercase letters and single spaces.

Examples. dictionary = ["cat","bat","rat"]dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"sentence = "the cattle was rattled by the battery" gives "the cat was rat by the bat""the cat was rat by the bat"

Editorial — approach, complexity, follow-ups

Build one trie from the roots, then walk each sentence word through it. Because a trie walk visits prefixes in increasing length order, the first end-of-word marker you meet is necessarily the shortest matching root — so you return immediately and never compare candidate lengths.

Time $O(\text{total dictionary characters} + \text{total sentence characters})$ . Space $O(\text{dictionary characters})$ .

The third test case is the one that matters: ["catt","cat",...]["catt","cat",...] contains both "catt""catt" and "cat""cat", and the answer must use "cat""cat". A solution that walks to the end of the word and keeps the last marker found, or that sorts the dictionary by length and checks prefixes with startswithstartswith, gets this wrong or does far more work.

The brute-force alternative — for each word, test every root with word.startswith(root)word.startswith(root) — is $O(\text{words} \times \text{roots} \times L)$ . With 1000 roots and a $10^6$ -character sentence that is too slow, which is exactly why the trie is wanted.

Follow-ups you should expect: “Longest matching root instead?” — keep walking and remember the last marker seen. “What if roots can be added dynamically?” — inserting into the trie is $O(L)$ , so nothing changes. “Preserve multiple spaces / punctuation?” — split()split() collapses whitespace, so switch to a manual scan or re.splitre.split and say so.

LC 211 — Design Add and Search Words Data Structure · Medium

Problem. Implement WordDictionaryWordDictionary with addWord(word)addWord(word) and search(word)search(word), where the searched word may contain .. as a wildcard matching any single character.

Constraints. 1 <= len(word) <= 251 <= len(word) <= 25, lowercase letters for addWordaddWord; searchsearch words may contain up to 2 dots (and up to 3 in the harder tests). At most 10^410^4 calls.

Example. Add "bad""bad", "dad""dad", "mad""mad". Then search("pad")search("pad") is FalseFalse, search("bad")search("bad") is TrueTrue, search(".ad")search(".ad") is TrueTrue, search("b..")search("b..") is TrueTrue.

Editorial — approach, complexity, follow-ups

addWordaddWord is the standard insert. searchsearch can no longer be a simple loop, because a .. has no single child to descend into — it must try all of them. That makes it a DFS with backtracking over (node, index)(node, index) pairs.

Time for addWordaddWord: $O(L)$ . For searchsearch: $O(L)$ when there are no wildcards; worst case $O(|\Sigma|^{d} \cdot L)$ where dd is the number of dots, since each dot multiplies the branching. With d <= 3d <= 3 and |Σ| = 26|Σ| = 26 that is bounded and fine. Space $O(L)$ for the recursion.

The length check matters too. search("b.")search("b.") is FalseFalse because every stored word has length 3 — reaching the end of the search string must coincide with a stored word ending, which is what i == len(word)i == len(word) plus the marker test enforces. Likewise search("....")search("....") is FalseFalse: four wildcards cannot match a three-letter word. A solution that returns TrueTrue as soon as it runs out of pattern gets both wrong.

Follow-ups you should expect: “Support ** (zero or more characters)?” — much harder; the DFS must also try consuming nothing and staying at the same node, and you need memoisation on (node_id, index)(node_id, index) to avoid blow-up. “Many dots?” — group stored words by length first, so a search only explores words of the matching length. “Delete a word?” — clear the marker and prune childless nodes upward.

LeetCode problem set

#	Problem	Difficulty	The twist
208	Implement Trie (Prefix Tree)	Medium	The base structure; the end-of-word marker is the whole point
648	Replace Words	Medium	Stop at the first marker to get the shortest root free
211	Design Add and Search Words Data Structure	Medium	Wildcards turn the walk into a DFS; skip the marker key
720	Longest Word in Dictionary	Medium	A word qualifies only if every prefix is also a word — check markers all the way down
677	Map Sum Pairs	Medium	Store a value per word; sum the whole subtree under a prefix
1268	Search Suggestions System	Medium	Walk to each prefix, then collect the 3 lexicographically smallest below it
421	Maximum XOR of Two Numbers in an Array	Medium	A bitwise trie — insert 32-bit paths, then greedily take the opposite bit
212	Word Search II	Hard	One grid DFS carrying a trie node — prunes against the whole dictionary at once

Interview follow-ups

They ask	What they’re checking	The answer
“Why a trie and not a hash set?”	Whether you know the actual win	A set matches exact lookup; a trie wins on prefix queries and on pruning a search against a whole dictionary
“Dict or a node class?”	Judgement	Dicts are shorter and interview-friendly; a class is more readable and avoids the marker-in-`items()items()` trap
“Why the end-of-word marker?”	Understanding vs. memorisation	It distinguishes “a word ends here” from “a word passes through here” — without it `search("app")search("app")` is wrong after inserting `"apple""apple"`
“Space complexity?”	Precision	$O(n \cdot L \cdot \\|\Sigma\\|)$ worst case with array children; a dict makes it $O(\text{total characters})$ in practice
“Implement delete”	Depth	Clear the marker, then prune upward while a node has no children and no marker
“How does a trie help on LC 212?”	The key insight	One DFS carries a trie node; when the path leaves the trie, no word can match, so the branch dies immediately
“Compress it?”	Breadth	A radix tree / Patricia trie merges single-child chains; suffix automata and Aho-Corasick are the next tier for multi-pattern matching

Edge-case checklist

Word that is a prefix of another — insert "apple""apple" then check "app""app"; the reason the marker exists.
Insert both "app""app" and "apple""apple" — both markers must survive on the same path.
Empty string — insert("")insert("") marks the root; decide whether that is legal and be consistent.
Searching a longer word than anything stored — search("appl")search("appl") and search("....")search("....") must be FalseFalse.
Searching a shorter pattern — search("b.")search("b.") against 3-letter words is FalseFalse; the end-of-pattern check must coincide with a marker.
The marker key during wildcard iteration (LC 211) — skip it, or you will recurse into a boolean.
Duplicate inserts — idempotent with this design; no special case needed.
Characters outside the assumed alphabet — a dict handles them; a 26-slot array raises IndexErrorIndexError.

Recap

A trie stores words along shared character paths, making prefix queries $O(L)$ regardless of how many words are stored.
node = node.setdefault(ch, {})node = node.setdefault(ch, {}) plus a "$""$" marker is a complete trie in six lines — no node class required.
The end-of-word marker is what separates searchsearch from startsWithstartsWith. Omitting it is the number-one trie bug.
A wildcard turns the walk into a DFS that branches into every child — and you must skip the marker key while iterating.
The biggest win is pruning: carrying a trie node through another search (a grid DFS, a recursion) kills branches that no dictionary word can extend, which is what makes LC 212 feasible.
“Prefix” need not mean characters — a bitwise trie solves maximum-XOR problems in $O(32n)$ .
If you only need exact lookup, use a setset. A trie earns its memory only when prefixes matter.

Next: the Search and Selection patterns — binary search on rotated arrays, quickselect, and heaps.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Trie Patterns

What you’ll learn

The cue

The template — a trie in six lines

Complexity, and what a trie actually buys

The variant map

Practice — real LeetCode problems

LC 208 — Implement Trie (Prefix Tree) · Medium

LC 648 — Replace Words · Medium

LC 211 — Design Add and Search Words Data Structure · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?