The Trie Pattern
A tree where each edge is a character, so words sharing a prefix share a path. Lookup cost depends on the length of the word rather than the number of words stored.
3
Interactive problems1
Free to openHow to recognise a trie problem
The problem involves prefixes — autocomplete, prefix search, word dictionaries — or repeatedly checks membership of many strings. Grid word-search problems use a trie to prune impossible branches early.
Time and space complexity
O(L) per insert or search, where L is word length, independent of how many words are stored. Space is O(total characters) in the worst case.
Trie practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Related patterns and concepts
The underlying technique is covered from first principles in the trie lesson in the DSA visualizer curriculum. Trie is one of the 16 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.