Which data structure is best for implementing a prefix search (autocomplete)?

• A. Hash Table
• B. Trie
• C. Graph
• D. Linked List

Answer: (B)

Prefix-based lookup efficiency is best served by a Trie, a prefix tree that stores words by sharing common prefixes. As you type a prefix, you follow the path for each character; the node you reach represents all words that start with that prefix. From there, you can quickly enumerate all completions by traversing the subtree, giving fast autocomplete suggestions. Insertion and locating the prefix are proportional to the length of the word or prefix, making the operations efficient. A hash table, while great for exact lookups, doesn’t support fast prefix search without extra work like storing every possible prefix. A graph or a linked list doesn’t provide the natural, shared-prefix structure that enables quick traversal to all matching words. With a Trie, you get near-instant prefix navigation and a straightforward way to gather matching words, which is ideal for autocomplete.