aloalgoTrie Summary
A quick reference for trie techniques and problems to practice. A trie (also known as a prefix tree) is a specialized tree data structure designed for efficient string operations. Unlike a hash set that treats each word as an opaque key, a trie stores words character by character, allowing words with shared prefixes to share the same nodes in the tree.This shared-prefix structure is what makes tries powerful for autocomplete systems, spell checkers, and prefix-based search problems. While tries use more memory than a simple hash set, they provide unique capabilities that no other data structure can match efficiently, particularly when you need to find all words matching a given prefix or pattern.Key Concepts
The table below summarizes the core operations of a trie. Each operation traverses the tree one character at a time, making the time complexity proportional to the length of the word or prefix rather than the number of words stored.| Concept | Description |
|---|---|
| TrieNode | Contains children map and is_end flag |
| Insert | Create nodes for each character, mark end |
| Search | Traverse nodes, check is_end at last node |
| StartsWith | Traverse nodes, return true if all found |
| Prefix Search | Find node, then DFS to collect words |
Complexity
| Operation | Time |
|---|---|
| Insert | O(m) |
| Search | O(m) |
| StartsWith | O(m) |
| Get all with prefix | O(m + k) |
When to Use a Trie
Tries are the right choice when your problem involves any of the following:- Prefix matching: Finding all words that start with a given prefix. This is the classic trie use case, seen in autocomplete and search suggestion systems.
- Word validation in grids: Problems like Word Search II require checking if strings formed by adjacent cells match dictionary words. A trie allows you to prune invalid paths early during the grid traversal.
- Wildcard matching: Searching for words where some characters are unknown (e.g., "c.t" matching "cat" and "cut"). A trie supports this by branching into all children when encountering a wildcard character.
- Longest common prefix: Finding the longest prefix shared by a set of strings. Simply traverse the trie until a node has more than one child.
Chapters
- Introduction to Trie - What problem tries solve
- Trie Implementation - Insert, search, startsWith
- Trie Applications - Autocomplete, word search, wildcards
Practice Problems
Medium
Hard
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.