← Algo Playground
STRINGS · PREFIX TREES

See the tree behind autocomplete.

A trie stores words one character at a time. Words that begin alike share the same path.

THE PREFIX TREE

One edge. One character.

Learning dictionary
Prefix pathMatching subtreeComplete word

SEARCH TRACE

Build the dictionary

Insert cart to reuse c → a → r and add just one new node. Insert ca to mark an existing node as a complete word.

WHY A TRIE?

Find the prefix. Explore below it.

  1. Start at the root. It represents the empty prefix.
  2. Follow one edge per letter. Searching “car” follows c → a → r. Other branches are skipped.
  3. Collect words below that node. A double ring means a word ends here. “car” can be a word and still lead to “care”.

Finding a prefix of length p takes O(p) child lookups. Listing completions takes additional work to visit their branches and produce the words.

Diagram reference: USF’s Trie (Prefix Tree) visualization ↗