Trie
The Intuition
Picture your phone's keyboard as you type a text message. You press "c" and it suggests "call," "can," "car," "cat." You press "a" next, and the suggestions narrow to "call," "can," "car," "cat." Press "r" and now it's just "car," "card," "care." Each letter you type walks you one level deeper into a branching tree of possibilities, pruning everything that doesn't match your prefix so far.
That branching tree is a trie. The root is empty. Its children are all possible first letters. Each of those children has children for all possible second letters, and so on. The path from the root to any node spells out a prefix. Some nodes have a flag that says "a complete word ends here." The path r-o-o-t spells "root," and that final "t" node is flagged. But the "roo" node is not flagged because "roo" isn't a word.
Searching for a word means walking the tree one letter at a time. Start at the root, follow the "c" branch, then the "a" branch, then the "t" branch. If you arrive at a flagged node, the word exists. If you hit a dead end (no branch for the next letter), the word isn't in your dictionary. Prefix search is even simpler: you just need to reach the node, flagged or not. If the node exists, some word starting with that prefix exists.
Insertion works the same way. Walk down the tree, creating new nodes for any letters that don't have branches yet. When you've placed the last letter, flip the "end of word" flag on. Every word that shares a prefix with an existing word reuses the same nodes up to the point where they diverge. "car" and "cat" share the c-a path and only split at the third letter. That shared structure is what makes tries so space-efficient when your dictionary has lots of words with common beginnings.
Autocomplete, spell checking, word search in a board, prefix matching, IP routing (longest prefix match), or any problem involving shared prefixes across many strings.
- Exact match only without prefix queries (use hash map)
- Patterns with wildcards in the middle (use regex or suffix tree)
- Very long strings with no shared prefixes (hash map is more space efficient)
Variations:
- Standard Trie: Basic insert/search/startsWith operations.
- Trie with counts: Track how many words pass through or end at each node.
- Compressed Trie (Radix Tree): Merge chains of single-child nodes for space efficiency.
- Trie + Backtracking: Used for word search problems on boards.
- Empty string insertion or search
- Single character words
- All words share the same prefix
Key Points
- •Each node stores children (hash map or array of 26 for lowercase)
- •Mark end-of-word with a boolean flag
- •Insert, search, and prefix search all run in O(L) where L = word length
- •Space-efficient when many words share common prefixes
- •Can be extended with counts, links to other data structures, etc.
Code Template
1 class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end = False
5
6 class Trie:
7 def __init__(self):
8 self.root = TrieNode()
9
10 def insert(self, word):
11 node = self.root
12 for ch in word:
13 if ch not in node.children:
14 node.children[ch] = TrieNode()
15 node = node.children[ch]
16 node.is_end = True
17
18 def search(self, word):
19 """Returns True if exact word exists."""
20 node = self._find(word)
21 return node is not None and node.is_end
22
23 def starts_with(self, prefix):
24 """Returns True if any word starts with prefix."""
25 return self._find(prefix) is not None
26
27 def _find(self, prefix):
28 node = self.root
29 for ch in prefix:
30 if ch not in node.children:
31 return None
32 node = node.children[ch]
33 return nodeCommon Mistakes
- Not marking end-of-word (prefix 'app' would match as word 'app' even without the flag)
- Confusing search (exact match) with startsWith (prefix match)
- Memory overhead when words have few common prefixes