1Understand
The idea
A trie stores words character by character along paths from the root, so every word with the same prefix shares the same first nodes. Insert and search cost O(length of the word), whatever the number of words stored, and every word with a given prefix sits under one node.
Intuition
A trie stores words character by character along paths from the root, so words that share a prefix share those first nodes. Insert and search cost O(length), independent of how many words are stored.
Prefix search is the killer feature: every word with a given prefix sits under one node. Autocomplete, word search boards and XOR tries (bit tries) all use the same spine.
Mark word ends explicitly so "app" and "apple" can coexist.
What you will be able to do
- Mark word ends explicitly
- Combine a trie with DFS
When to use it
- Many words sharing prefixes
- startsWith queries
- Word search with a dictionary
2See it
Walkthrough
Insert and search
Insert "app", search "app" / "ap".
1 / 5
node
- ∅ empty
Root children empty. Create edge for "a".
Live template
Line 1 active
Complexity: time O(L) per op, space O(total chars)
Build O(total characters). Query O(length). Space can be large with sparse alphabets, nested dicts are fine in Python; fixed-size arrays of 26 win when the alphabet is tiny and dense. Hash sets find whole words but cannot share prefix structure.
Read the walkthrough as text
Insert and search. Insert "app", "apple", then search "app" and prefix "ap".
- From root, follow/create
a → p → p, mark end on the third node. - Insert
"apple": reusea-p-p, then addl → eand mark end. - Search
"app": walk three edges and check end flag, true. - Prefix
"ap": walk two edges, node exists, so some word has that prefix.
In code:
class Node:def __init__(self):self.children = {}self.end = False
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Insert / search / startsWith
Example. Implement trie dictionary operations.
How. Walk children dict per char; end flag marks complete words.
Wildcard search
Example. Search with '.' matching any letter.
How. DFS at node with branch all children on dot, else single char edge.
Word search II (trie + grid DFS)
Example. Find all dictionary words in a grid.
How. Trie of words; DFS grid pruning when prefix not in trie.
Autocomplete / top suggestions
Example. Return top k words with prefix.
How. Collect words under prefix node; sort by freq or heap k bests.
Longest common prefix
Example. Longest shared prefix of word list.
How. Walk trie until fork or word end; path chars form answer.
Binary trie over bits (maximum XOR)
Example. Max XOR pair in array.
How. Insert 32-bit bits; greedy opposite bit when available.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
No end marker
Why it happens. Reaching node after last char means word exists.
How it fails. search("app") true because "apple" was inserted, prefix mistaken for word.
Fix. Insert sets node.is_end; search requires is_end true.
Rescanning the word list
Why it happens. Linear scan word list for each prefix query is fine for small n.
How it fails. Thousands of startsWith queries each scan whole dictionary, O(words·len) per query.
Fix. Trie shares prefixes, one walk per query.
Found words not pruned
Why it happens. DFS explores all paths even after word found.
How it fails. Word search II revisits found words and duplicates in output.
Fix. Mark trie word found and prune branch; or remove word from trie node.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.