TTopic
Tries Problems
Trie problems — prefix-tree implementations for word lookup, autocomplete, and prefix-based search.
Medium · 2
Hard · 1
A trie (prefix tree) is the optimal data structure whenever you need fast prefix search across a corpus of strings — autocomplete suggestions, spell-check, dictionary matching, longest-common-prefix queries. It trades higher memory consumption for O(L) lookup where L is the word length, regardless of how many words the trie contains.
In interviews, tries show up in two roles. The first is direct implementation — design and build a trie that supports insert, search, and startsWith. The second is trie-as-accelerator — combine a trie with backtracking or DFS to solve word-search-on-a-grid problems where you need to prune early when the current path can't extend to any dictionary word. The combination is the canonical solution to Word Search II.
The Ratta trie track covers Implement Trie (Prefix Tree), Design Add and Search Words Data Structure (with wildcard support), and Word Search II. Each problem includes a full TrieNode class, child-pointer management, and tested implementations in C++, Java, Python, and Go.