Overview
A Trie represents each key as a path of characters or tokens from the root. Shared prefixes occupy shared nodes, making prefix queries natural.
FoundationSource checked
Trie
Stores strings by sharing prefixes along paths through a tree.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Prefix Tree
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
Core Concepts
prefix treeterminal markerchild mapshared prefix
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(m)
Average
O(m)
Worst
O(m)
Space
O(nm)
When to Use
- Use it for prefix lookup, autocomplete, and dictionaries over strings.
- Use it when many keys share prefixes.
- Use compressed variants when memory use matters.
When Not to Use
- Avoid it for small key sets where a hash table is simpler.
- Avoid naive child arrays when the alphabet is large and sparse.
- Avoid it when approximate matching is needed without additional traversal logic.
What It Does
- Shares prefixes between strings
- Supports prefix-based lookup
Use Cases
- Autocomplete
- Dictionary lookup
- Prefix matching
Inputs
- Strings or token sequences
Outputs
- Prefix tree
- Lookup and prefix results
Pseudocode
- 1.Start at the root
- 2.For each character in the string:
- 3.Follow the matching child if it exists
- 4.Create a child if needed during insertion
- 5.Mark the final node as a complete word
Canonical Example
- Input
- operations = insert 5, insert 2, query 5
- Output
- query result = found
- Explanation
- Trie: The structure stores data so later operations can answer efficiently.
Implementation Notes
- Store an end-of-key marker at terminal nodes.
- Choose child maps, arrays, or compressed edges based on alphabet and memory needs.
- Normalize input consistently before insertion and lookup.
Common Pitfalls
- Forgetting to mark terminal nodes separately from internal prefix nodes.
- Using memory-heavy child arrays for sparse alphabets.
- Ignoring Unicode normalization or tokenization rules.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow words branching only when their prefixes differ.
Step 1 of 5: Start at the root
prefix-treeNotes
Tries make prefix operations efficient at the cost of extra pointer or map overhead.
Sources (1)
What each reference supports for this entry.
Algorithms, 4th Edition
BookAlgorithms textbook support for Trie's data-structure operations and practical implementation model.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byAho-Corasick
Pattern Matching · Core
Aho-Corasick builds a pattern trie before adding failure links.
Compare with thisConceptual neighborsBK-Tree
Data Structures · Core
Both can support dictionary-like lookup, but BK-trees organize items by metric distance.
Compare with thisConceptual neighborSuffix Tree
Data Structures · Core
Both store strings through shared-prefix tree structure.
Compare with thisRelationships
View full relationship pageUsed byAho-Corasick
Aho-Corasick builds a pattern trie before adding failure links.
Conceptual neighborSuffix Tree
Both store strings through shared-prefix tree structure.
Related Algorithms
Tags
Data StructureTreePrefix TreeStrings