Course contentsShow
← System Design
Lesson 1758 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Trie Data Structure for Prefix Matching

How tries efficiently store and retrieve strings by prefix, making them ideal for typeahead suggestions.

Trie Data Structure for Prefix Matching

You'll learn: How tries efficiently store and retrieve strings by prefix, making them ideal for typeahead suggestions in search systems.

What Is a Trie?

A trie (pronounced "try," from retrieval) is a tree-like data structure where each node represents a single character of a string. Words sharing common prefixes share the same path from the root, making prefix lookups extremely fast.

Think of it like a filing system: instead of storing "cat," "car," and "card" separately, you store c → a, then branch into t (for "cat") and r (which branches further into "car" and "card"). All words starting with "ca" share the first two nodes.

Why Tries Excel at Typeahead

When a user types "se" into a search box, you need to find all matching suggestions instantly. With a trie:

  1. Navigate from root → 's' → 'e' (2 operations)
  2. Collect all words in the subtree below 'e'

This beats scanning millions of strings or even binary search. The lookup time is O(m) where m = prefix length, independent of total vocabulary size.

Key Properties

  • Space-efficient for shared prefixes (many words → fewer nodes)
  • Fast prefix matching: Walk down the prefix path once
  • Easy enumeration: All completions live in one subtree
  • Supports ranking: Store metadata (frequency, popularity) at terminal nodes to rank suggestions

Storage Considerations

Each node may store:

  • Character or edge label
  • Children pointers (array or hashmap)
  • End-of-word flag
  • Metadata (completion count, score)

For massive vocabularies, tries can be memory-intensive, but compression techniques (radix tries, LOUDS) help at scale.

Key Takeaway:
Tries organize strings by shared prefixes, enabling O(prefix_length) lookup for typeahead suggestions—far faster than scanning or searching unsorted data.