Stage 1 · Code
Linked Lists & Trees
Trie (Prefix Tree)
A tree of characters that answers 'does this word exist?' and 'does any word start with this prefix?' in O(L) — optimal for string dictionaries.
The Structure
A Trie (pronounced 'try') is a tree where each node holds a single character and an array (or map) of children — one per possible next character. A boolean flag marks the end of a complete word. The root is typically an empty node. Unlike a hash set, a trie shares prefixes: 'cat' and 'car' share the 'ca' path, so storing both requires only 5 nodes instead of 8 characters.
Trie structure
Each edge represents a character. The 'c' node has children 'a', which in turn has 't' and 'r'. Searching for 'ca' walks root→c→a and reports the path exists (prefix match). Searching for 'cat' walks further to 't' and finds the end-of-word flag.
Operations
Trie vs Hash Set
A hash set can answer 'does word X exist?' in O(1) average. Only a trie can answer 'does any word start with prefix X?' in O(L). This makes tries essential for autocomplete, spell checkers, IP routing (longest prefix match), and any problem where you walk character by character against a dictionary.
When to Use
- Prefix matching: 'Does any stored word start with this substring?' — hash sets cannot answer this efficiently.
- Dictionary with backtracking: Search a 2D board for words (LeetCode 79, 212) — the trie prunes invalid paths early.
- Autocomplete / suggestion: Walk the prefix, then DFS from that node to collect all completions.
- Lexicographic ordering: A DFS of the trie yields words in sorted order.
- Word break / pattern matching: Check if a string can be segmented into dictionary words (LeetCode 139, 140).
- Not for: Single-word lookups by exact key (hash set is simpler and faster). Numeric keys. Small, static dictionaries (a sorted array + binary search may suffice).
Problems
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.