A prefix tree that makes word lookup, autocomplete, and prefix counting linear in word length.
What a trie is
A trie stores strings as paths from a root: each edge is a character, each node a prefix, and shared prefixes share nodes. Insert and lookup walk one node per character - O(L) for a word of length L, independent of how many words are stored. A hash set matches that for exact lookups; the trie's edge is everything prefix-shaped: 'is any word starting with pre-', 'list completions', 'count words under this prefix'.
A node is a children map (array of 26 for lowercase, hash map for open alphabets) plus an isEnd flag. The flag is load-bearing: 'car' being a PATH in the trie does not mean 'car' was INSERTED - it may only exist as a prefix of 'carpet'. Node existence answers prefix questions; isEnd answers word questions.
How to recognize it
Signals: autocomplete or type-ahead, 'starts with' queries, dictionary membership with wildcards, replacing words by their shortest root, or searching MANY words at once through a shared structure (word search II). The moment a problem repeats prefix work across many strings, a trie amortizes it.
Counter-signal: exact membership only, no prefix semantics - a hash set is simpler and faster in practice. Choosing the trie only when prefixes matter is itself a signal of judgment.
The core implementation
Insert: walk from the root, creating missing children, and set isEnd on the final node. Search: walk; fail on a missing child; at the end, return isEnd for word search or plain true for prefix search - the two methods differ by exactly that flag.
pseudocode
class Node: children = {}, isEnd = false
def insert(word):
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = Node()
node = node.children[ch]
node.isEnd = true
def search(word): # exact word
node = walk(word)
return node != null and node.isEnd
def startsWith(prefix): # any word with this prefix
return walk(prefix) != null
Wildcards and multi-word search
A '.' wildcard turns lookup into DFS: at a dot, recurse into every child; at a letter, follow that child only. Worst case degrades toward visiting many nodes - say so.
The heavyweight use is many-words-in-a-grid (word search II): build one trie of all query words, then run a single grid DFS that walks the trie in lockstep with the board. Dead prefixes prune instantly, all words are found in one traversal, and marking found words (clearing isEnd) prevents duplicates. One structure replaces running word-search once per word.
Common pitfalls
Conflating node existence with word membership - forgetting isEnd makes every prefix count as a word.
Memory blindness: 26-pointer arrays per node get heavy for large dictionaries; a hash-map-per-node trades constant factor for space. Mention the trade.
In grid+trie DFS, checking the trie after moving instead of pruning before recursing - the pruning is the entire performance story.
Failing to unmark visited cells on backtrack in word search II, or re-reporting a word found twice (clear isEnd or track a found-set).
Rebuilding the trie per query. It is a build-once, query-many structure; if there is one query ever, reconsider the hash set.
Worked examples
1. Implement Trie (prefix tree)medium
Implement insert(word), search(word), and startsWith(prefix) for a trie.
Design the node first: children (array-of-26 or map) plus isEnd. Everything else is walking.
Insert walks and creates: one node per missing character, isEnd = true at the end.
search and startsWith share the same walk; they differ only in whether the final node must carry isEnd. Factoring the walk into a helper makes the distinction impossible to get wrong.
All operations O(L) time; memory O(total characters inserted) worst case, less with shared prefixes.
pseudocode
def walk(s):
node = root
for ch in s:
if ch not in node.children: return null
node = node.children[ch]
return node
insert(word): create-as-you-walk; final.isEnd = true
search(word): walk(word) exists and isEnd
startsWith(p): walk(p) exists
Remember: Factor out the walk: word-vs-prefix is a one-flag difference at the final node, and isEnd is what separates 'car' from merely 'the start of carpet'.
2. Design add and search words (wildcard '.')medium
Support adding words and searching with '.' matching any single character.
Without dots, this is plain trie search. A dot means 'any child works here' - the search must branch, so it becomes DFS over (trie node, position in query).
Letter at position i: follow exactly that child or fail. Dot at position i: recurse into every child; succeed if any branch does.
Base case: at the query's end, isEnd on the current node decides - a dot cannot rescue a path that isn't a whole word.
Cost is O(L) for dot-free queries and up to O(26^dots x L) with them - stating the degradation is part of a complete answer.
pseudocode
def dfs(node, i):
if node is null: return false
if i == len(query): return node.isEnd
ch = query[i]
if ch == '.':
return any(dfs(child, i+1) for child in node.children.values())
return dfs(node.children.get(ch), i+1)
dfs(root, 0)
Remember: A wildcard converts the single trie walk into branching DFS - deterministic steps for letters, fan-out only where the dots are.
3. Word search II (many words in a grid)hard
Given a letter grid and a list of words, find every word that can be formed by adjacent cells without reusing a cell.
Running single-word search per word repeats grid work per word. Instead, build one trie of ALL words and walk grid and trie together.
DFS from each cell: entering a cell, descend to the trie child for its letter - no child means no word continues here, prune immediately.
On a node with isEnd, record the word and clear isEnd (no duplicate reports). Mark the cell visited, recurse 4 ways, unmark on backtrack.
Optionally delete childless trie nodes as they empty - the trie shrinks as words are found, tightening pruning. This trie-guided-DFS composition is a favorite hard-question shape.
pseudocode
build trie of all words (store word at its end node)
for each cell (r, c): dfs(r, c, root)
def dfs(r, c, node):
child = node.children.get(grid[r][c])
if child is null: return # prune: no word this way
if child.word: results.add(child.word); child.word = null
mark (r, c) visited
for neighbor in 4 directions in bounds and unvisited:
dfs(neighbor, child)
unmark (r, c)
Remember: Search all words at once: the trie IS the shared search frontier, and a missing child prunes every word with that dead prefix in one comparison.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1Why does a trie node need an isEnd flag?
To terminate traversal loops
✓ Because a node's existence only proves some word passes through it - the flag records that a word ends exactly there
To support deletion
It is optional when the alphabet is small
After inserting only 'carpet', the path c-a-r exists but 'car' was never added. search('car') must fail while startsWith('car') succeeds - isEnd is exactly that distinction.
2When does a trie beat a hash set for a strings problem?
Always, since O(L) beats O(1)
✓ When prefix semantics matter - autocomplete, startsWith, wildcards, or sharing traversal across many words - not for plain exact membership
When strings are short
When memory is scarce
Hash sets answer exact membership in O(L) too (hashing reads the string) and are simpler. The trie's structure pays off only when the tree shape itself - shared prefixes - is being exploited.
3In word search II, what does walking grid-DFS and trie in lockstep buy?
Lower memory usage
✓ A missing trie child prunes every query word sharing that dead prefix at once, and all words are found in one grid traversal
It avoids marking cells visited
Sorted output
The trie aggregates all words' prefixes; one failed child lookup eliminates the whole family of words down that branch. Per-word search re-explores the grid for each word and can't share that pruning.
4How is a '.' wildcard handled during search?
Skip the character entirely
✓ Recurse into every child of the current node, succeeding if any branch completes
Match only vowels
Convert the query to a regex
The dot removes determinism at one step, so the search fans out across all children there - DFS with branching factor up to the alphabet size at each dot, deterministic elsewhere.
Frequently asked questions
Array of 26 children or a hash map per node?
Array: fastest access, fixed 26-slot cost per node even when sparse - right for dense lowercase dictionaries. Hash map: pays per actual child, handles any alphabet - right for sparse or unicode data. Naming the trade is usually worth more than the pick.
How do I delete a word from a trie?
Clear isEnd at the final node; then, walking back up, remove nodes that have no children and no isEnd. Recursive deletion returning 'can my parent drop me' is the clean formulation. Many problems only need the isEnd clear (as in word search II's duplicate prevention).
How much memory does a trie use?
Worst case one node per inserted character - heavy for large dictionaries with array children (26 pointers each). Shared prefixes reclaim a lot in practice; compressed tries (radix trees) merge single-child chains when memory truly matters.