Trie
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.
Interactive problems
Free to open
How do you 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.
What is the time complexity of the trie pattern?
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++.
Trie problems by difficulty and complexity
The difficulty, running time and extra space of every trie solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Introduction to Tries (Prefix Trees) | Medium | Ω(1) | Θ(L) | O(L) | O(N·L) |
| Implement Trie (Prefix Tree) | Medium | Ω(1) | Θ(L) | O(L) | O(N·L) |
| Prefix Matching | Medium | Ω(1) | Θ(L) | O(L) | O(1) |
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 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree