Data structures
Tries
Share prefixes across strings.
Understand the problem
Each edge represents a character and each node can mark the end of a word. Prefix lookup follows the path without enumerating all stored strings.
Make it concrete
Autocomplete for app traverses a→p→p before collecting matching words.
Trade-offs and pitfalls
Tries trade memory for prefix operations; compressed edges can reduce overhead.
Check your understanding
Why must word termination be stored separately from child existence?
Practice this topic