Skip to content
BENIBIX Learn

Trie

Development🧮 Algorithms & Data StructuresData Structures

Also known as Prefix Tree, Digital Tree

A tree that stores words letter by letter. Shared starts share a branch.

Think of it like

Think of it like a word tree. Words that start the same share the same branch.

Example

Lucy types "ca" into a search box. A trie of 100,000 words hands back cat, cake and car at once.

Why it matters

Search boxes that guess the next word, and spell checkers, are built on it.

Definition

A trie is a tree that stores words one letter per step. Words that begin with the same letters share the same path from the root. To find every word that starts with "ca", you walk down c, then a, and read everything below. The time to find a word depends on its length, not on how many words are stored. Search boxes use tries to suggest words as you type.

Common mistake

Using a trie for a small word list. A sorted list or a set is simpler and fast enough.

Key takeaways

  1. 1
    One letter per step. Down from the root.
  2. 2
    Shared starts. Share one branch.
  3. 3
    Speed by length. Not by word count.