Step 1 Understand it
Remember it by
Prefixes? Store words letter by letter in a tree, so shared beginnings are stored once.
Watch it happen
Read the animation as text
- A trie stores words letter by letter along paths from the root. Words that share a start share a path. It starts as just the root.
- insert 'app': create a → p → p, then mark the last p as the end of a word (green ring).
- insert 'apple': a → p → p already exist — walk them. Create only l → e, and mark e as a word end.
- search('app'): follow a → p → p. The last p has the word-end ring: True.
- search('ap'): follow a → p. The path exists, but this p has no word-end ring — 'ap' was never inserted: False.
- startsWith('ap'): follow a → p. The path exists, and that is all a prefix check needs: True.
- search('apt'): follow a → p, then look for 't'. There is no such child: False. It took 3 steps, not a scan of every word.
- Results: True, False, True, False. Each lookup costs the length of the word, however many words are stored.
The idea
A trie is a tree where each edge is a letter and each path from the root spells a prefix. Looking up a word or a prefix takes as many steps as the word has letters, however many words are stored.
Picture it
flowchart TD
R(("root")) --> A(("a")) --> P1(("p")) --> P2(("p ✓")) --> L(("l")) --> E(("e ✓"))
R --> B(("b")) --> A2(("a")) --> T(("t ✓"))Analogy
A phone's autocomplete. Type 'ap' and it walks a → p, then shows everything below: app, apple, apply.
Where the analogy breaks
Autocomplete feels instant for any phrase. A trie only helps with beginnings of words; it can't find a word by its middle or end.
More detail
What it is
A Trie (pronounced 'try') is a special kind of tree specifically designed to store strings. Each node in the tree represents a single character. If you follow a path from the root down to a leaf, the characters along the way spell out a complete word! It's the ultimate data structure for Auto-Complete and Spell Checkers.
When to use it
- When you need to store a dictionary of words.
- When building Auto-Complete features (e.g., 'Find all words starting with
cat'). - When searching for strings character-by-character.
How it works
Instead of a standard left and right pointer, a TrieNode usually holds a HashMap or an array of 26 pointers (one for each letter of the alphabet). You also need a boolean flag isEndOfWord at each node to know if the path you've traveled actually forms a complete word, or is just a prefix.
Example walkthrough
Input: insert("cat"), insert("car"), search("cat")
- Insert 'cat': Root -> 'c' -> 'a' -> 't' (mark 't' as End).
- Insert 'car': Root -> 'c' -> 'a' -> 'r' (mark 'r' as End). Notice they effortlessly share the 'c' -> 'a' branch!
- Search 'cat': Follow 'c', follow 'a', follow 't'. Is 't' marked as End? Yes! Return true.
Result: true
Related patterns
- Trees: A Trie is literally just an N-ary tree.
Step 2 Recognise it
Words that signal it
- 'Prefix', 'starts with', 'autocomplete'
- Searching many words at once on a grid (Word Search II)
- Wildcard search where '.' matches any letter
- A dictionary of words checked letter by letter
Don't confuse it with
- Arrays & Hashing: Only whole-word lookups → a hash set is simpler. Prefix questions → trie.
- Backtracking: Word Search I (one word) is plain backtracking on a grid; Word Search II (many words) adds a trie so all words are searched in one pass.
Gut check
Are prefixes, or many words sharing beginnings, involved? → trie.
How to recognise it in an interview
The problem talks about 'Words', 'Dictionaries', 'Prefixes', or 'Auto-Complete'.
Step 3 The template
The general shape. Adapt it to each problem rather than learning one solution per problem.
class TrieNode:
def __init__(self):
self.children = {} # letter -> TrieNode
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_word = True
def _walk(self, text):
node = self.root
for ch in text:
if ch not in node.children:
return None
node = node.children[ch]
return node
def search(self, word):
node = self._walk(word)
return node is not None and node.is_word
def starts_with(self, prefix):
return self._walk(prefix) is not NoneThe same template in Java
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord = false;
}
class Trie {
private TrieNode root = new TrieNode();
public void insert(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
if (curr.children[c - 'a'] == null) {
curr.children[c - 'a'] = new TrieNode();
}
curr = curr.children[c - 'a'];
}
curr.isEndOfWord = true;
}
}Common mistakes
- Forgetting the end-of-word flag, so 'ap' is wrongly found after inserting 'apple'.
- Confusing search (needs the word-end flag) with startsWith (doesn't).
- In Word Search II, not removing found words, so the same word is reported twice.
Step 4 Watch it run
Two problems, traced step by step exactly as the code runs.
Easy example: Implement Trie
Input: insert 'app', insert 'apple', then four lookups
| operation | what happens | returns |
|---|---|---|
| insert 'app' | create a → p → p, mark the last p as a word end | – |
| insert 'apple' | a → p → p already exist; create l → e, mark e | – |
| search 'app' | follow a → p → p; is p marked as a word end? yes | True |
| search 'ap' | follow a → p; is p marked as a word end? no | False |
| startsWith 'ap' | follow a → p; the path exists | True |
| search 'apt' | follow a → p; no child 't' | False |
Result: True, False, True, False
Notice: 'ap' is a valid path but not a word: the end-of-word flag is the difference between search and startsWith.
Medium example: Add and Search Words (with '.' wildcards)
Input: words: bad, dad, mad · searches: '.ad', 'b..', 'pa.'
| search | path explored | returns |
|---|---|---|
| .ad | '.' → try 'b' → end of '.ad' at 'bad': word end? yes | True |
| b.. | '.' → try 'ba' → '.' → try 'bad' → end of 'b..' at 'bad': word end? yes | True |
| pa. | no 'p' after '' → dead end | False |
Result: True, True, False
Notice: A '.' means 'try every child' — a small depth-first search inside the trie.
def search(node, word, i=0):
if i == len(word):
return node.is_word
ch = word[i]
if ch == '.':
return any(search(child, word, i + 1) for child in node.children.values())
if ch not in node.children:
return False
return search(node.children[ch], word, i + 1)Step 5 Practise
Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.
Medium
-
Implement Trie Prefix Tree Medium
Build a structure with insert, search for a word, and check whether any word starts with a prefix.
Show answer
Technique: Trie
The clue: 'Starts with' a prefix.
The trick: Each node has children by letter and an end-of-word flag.
-
Store words and search with '.' matching any single letter.
Show answer
Technique: Trie + DFS for wildcards
The clue: Many word lookups with a wildcard letter.
The trick: Walk the trie normally; at a '.', try every child.
Hard
-
Word Search II Hard
Find all words from a list that can be traced in a letter grid.
Show answer
Technique: Trie + grid backtracking
The clue: Many words searched on the same grid.
The trick: Put all words in a trie and DFS the grid once, following trie children; stop early when no word has that prefix.
What to say in the interview
'Since we have many words that share the same starting letters, a Trie will drastically optimize our prefix matching from O(N*L) searching down to just O(L).'!
Follow-up prep
How do you delete a word from a Trie without deleting shared prefixes?