Trie Autocomplete
Prefix-tree lookup and subtree traversal generate suggestions without scanning the full vocabulary.
2024
Character-path sharing and depth-first suggestion collection.
System overview
A prefix tree stores words as shared character paths. Prefix traversal locates the matching subtree; depth-first collection generates completions. Lookup follows prefix length, with collection cost depending on the matching subtree.
Prefix to suggestions
- Typed prefix
- Character traversal
- Prefix node
- Subtree search
- Matching words
Finding the prefix and enumerating its suggestions are separate operations.