Interview OS
Back to Algorithms & Data Structures

Library

Tries

Prefix tree for string lookups.

Tree

Overview

A trie stores strings by shared prefixes, so lookups and prefix queries cost O(length) regardless of how many words are stored. It powers autocomplete, spell-check, and dictionary matching.

How it works

Tree
InsertStoreSearchOutputChar pathedges=charsNode mapchildren[]Walk prefixO(len)Use
ClientDataServiceEdge

Step by step, with examples

  1. 1

    Char path

    • Add words character by character.
  2. 2

    Node map

    • Children keyed by character.
  3. 3

    Walk prefix

    • Follow chars; flag word ends.
  4. 4

    Use

    • Autocomplete and prefix search.
    • Example: typeahead

Overview

A tree keyed by characters; O(L) insert/search where L is word length, independent of dictionary size.

When to use it

  • Autocomplete
  • Prefix matching
  • Word-search / dictionary problems

Common pitfalls

  • High memory for sparse alphabets
  • Forgetting end-of-word markers

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides