aloalgoIntroduction to Trie
A trie (pronounced "try") is a tree-like data structure used for storing strings. It's also called a prefix tree because it excels at prefix-based operations.What Problem Does a Trie Solve?
Imagine you have a dictionary of words and need to:- Check if a word exists
- Find all words starting with a prefix
- Implement autocomplete
- Validate words in a word game like Scrabble or Boggle
Trie Structure
Each node in a trie represents a character. The path from the root to a node spells out a prefix. Nodes are marked as "end of word" when they complete a valid word. The root node itself represents the empty string, and each edge corresponds to a character that extends the current prefix by one letter.In a typical implementation, each node contains a dictionary (or array) mapping characters to child nodes, plus a boolean flag indicating whether the current node marks the end of a complete word. This structure allows you to traverse the trie character by character, following edges that match the characters of your search string.Why Use a Trie?
| Operation | Hash Set | Trie |
|---|---|---|
| Check if word exists | O(m) | O(m) |
| Check if prefix exists | O(n * m) | O(m) |
| Find all words with prefix | O(n * m) | O(m + k) |
| Autocomplete suggestions | O(n * m) | O(m + k) |
Trie vs Other Data Structures
Use a Trie when:- You need prefix-based search or autocomplete
- You're doing word validation (like in word games)
- You need to find words matching a pattern
- You only need exact word lookup
- You don't care about prefixes
- Memory is a concern (tries can use more memory)
Common Interview Problems
Trie problems in interviews typically ask you to build a trie from scratch or use one to solve a string-related challenge efficiently. The key insight is that tries turn prefix matching from a linear scan into a simple tree traversal.- Implement Trie: Build insert, search, and startsWith operations. This is the foundational problem that tests your understanding of the data structure itself.
- Word Search II: Find all words from a dictionary in a grid. Combines trie traversal with backtracking on a 2D board.
- Autocomplete System: Return top suggestions for a prefix. Requires combining a trie with frequency tracking.
- Replace Words: Replace words with their shortest prefix in dictionary. Uses a trie to find the shortest matching prefix for each word in a sentence.
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.