What is a trie, and what problem does it solve well?

• A. A linked list used for indexing.
• B. A graph used for network routing.
• C. A hash table for fast lookups.
• D. A tree-like data structure for storing strings, enabling prefix-based searches.

Answer: (D)

A trie is a tree-like data structure where each node represents a character and paths from the root spell out strings. This setup makes it especially good for handling a large set of strings and performing prefix-based searches. When you want to know if a word exists or you want to find all words that start with a given prefix, you follow the path for that prefix and then explore the subtree beneath it. The operation time scales with the length of the word or prefix, not with the number of stored words, which makes lookups, insertions, and prefix queries fast. That efficiency is why tries are favored for features like autocomplete, spell-check dictionaries, and other prefix-search tasks. In contrast, a linked list or a hash table doesn’t natively support efficient prefix-based querying or the shared-prefix space-saving that a trie provides.