Trie (Prefix Tree)

Store strings as a tree of shared prefixes so lookups and prefix queries cost only the length of the word, independent of how many words you have stored.

Key ideas

  • —Each edge is a character; a path from the root spells a prefix.
  • —Lookup and insert are O(L) in the word length, not in the number of words.
  • —A trie is the right index when many searches share prefixes, as in word-grid puzzles.

Sharing prefixes

A trie collapses all words that start the same way onto a shared path, with a flag marking where complete words end. Because traversal follows one character per level, both insertion and exact lookup run in O(L) regardless of the dictionary size. That makes prefix queries — "is any word starting with these letters present?" — trivial and fast.

Tries inside a search

In Word Search II you must find many dictionary words inside a grid at once. Building a trie of the dictionary lets a single DFS over the grid prune the instant the current path is not a prefix of any word, instead of searching for each word separately. The trie turns "test every word" into "walk the grid once".

Practice this

Sources

← All lessonsNext: Bit Manipulation →