What is a trie (prefix tree)?

A trie (prefix tree) is a data structure that stores strings character by character, allowing efficient prefix search.

Each tree node represents a single character, and the path from the root to a node is the prefix of some string. A complete word ends at a node marked as the end of word.

Example:

For the words cat, car, dog the tree looks like this:

• Root → c → a → t (end of word) ↳ r (end of word)
• Root → d → o → g (end of word)

Main operations:

• Insertion: O(L), where L is the length of the word.
• Search: O(L).
• Prefix search: O(P), where P is the length of the prefix.

Advantages:

• Fast word lookup and prefix-based autocomplete.
• Large dictionaries can be stored without duplicating shared prefixes.

Disadvantages:

• Uses more memory than a hash table (many child pointers).