Tries: The Search Accelerator

A Trie (derived from "retrieval") is a multi-way tree structure used for storing strings. Unlike a Hash Table, where order is lost, a Trie stores strings by their Characters, allowing for incredibly fast prefix searches.

1. How a Trie Works

Each node in a Trie represents a single character. As you walk down a path (e.g., A -> P -> P -> L -> E), you form a word. Every node can have up to 26 children (one for each letter of the alphabet).

2. Perfect for Auto-complete

If you have 1 million words and want to find those starting with "prog", a Hash Table would have to scan everything. A Trie just jumps to the 'p-r-o-g' node and lists all its descendants. Search time is O(L), where L is the length of the word, independent of how many millions of words are in the dictionary.

3. The Memory Trade-off

Tries can be memory-heavy because every node has an array of pointers for children. We often use Compressed Tries (Radix Trees) where nodes with only one child are merged to save space.

4. Interview Mastery

Q: "When is a Trie better than a Hash Table?"

Architect Answer: "A Trie is superior for **Prefix Queries** (e.g., 'give me all words starting with 'arch'') and for finding the **Longest Common Prefix** across a set of strings. It also avoids the 'Hash Collision' problem. However, for simple exact-match lookups, a Hash Table is usually faster and more memory-efficient."