What is a trie (prefix tree) — and why autocomplete never scans the whole dictionary

You're building a search box with suggestions. The AI writes an honest solution:

const hints = words.filter(w => w.startsWith(query)).slice(0, 10);

On 300 words it flies. Then you load a 100,000-word dictionary. Now every keystroke is 100,000 comparisons. Someone types "pro", and the code runs through the entire dictionary three times. Including "apple" and "zebra", which obviously don't match.

Here's the trick: all the "pro" words already start the same way. Why store that beginning a hundred times? That one thought is what a trie is built on.

What a trie is, in one line

A trie (prefix tree) stores words so that shared beginnings are kept once, and words branch off from them.

It's pronounced "try" or "tree" — from retrieval. People still argue; both are in use.

Take the words "pro", "prod", "project" and "pry". As a trie:

p
└─ r
   ├─ o ●                ← "pro" ends here
   │  ├─ d ●             ← "prod"
   │  └─ j → e → c → t ● ← "project"
   └─ y ●                ← "pry"

Each node is one letter. The dot ● means "a real word ends here". The letters "p" and "r" are stored once for all four words.

How it searches

Find everything starting with "pro". The algorithm doesn't look at the dictionary at all. It walks the letters of the query:

1. From the root into the "p" branch.
2. From "p" into "r".
3. From "r" into "o". Done.

Three steps, because the query has three letters. It doesn't matter how many words the dictionary has — a hundred or a million. Steps = letters you typed.

The subtree under that node is the answer: every word starting with "pro". Walk it, collect the first 10, stop as soon as you have them.

In code, a node is a plain object whose keys are letters and values are the next nodes:

function insert(root, word) {
  let node = root;
  for (const ch of word) {
    node[ch] ??= {};
    node = node[ch];
  }
  node.end = true;
}

Search is the same loop without creating nodes. Missing letter? Then no word has that beginning at all. "Nothing found" comes back instantly.

Why it matters to you

Where you meet tries even if you never wrote one:

• Autocomplete. Search suggestions, city pickers, tags. Each new character is one step down from the previous node, not a fresh pass over the dictionary.
• Web server routing. Fastify finds which handler to run for /users/42/posts with a radix tree — a compressed trie. Paths sharing /users/ live in one branch.
• Spell checkers and T9 on old phones.
• Internet routers. Deciding where to send a packet means finding the longest matching address prefix — a textbook prefix-tree job.

The takeaway: if your task says "starts with…" and you have thousands of words or more, that's the signal. Prefix search is a trie's home turf.

Where it loses

Honestly, a trie isn't a silver bullet.

• Memory. Every letter is its own object. The tree easily takes several times more space than a plain word list. The compressed version, a radix tree, stores the chain "j → e → c → t" as one node "ject".
• Beginnings only. A trie can't find "ject" in the middle of a word. Searching anywhere in the text, or by meaning, needs other tools — like semantic search.
• Small lists. On 2–3 thousand words, filter finishes in a fraction of a millisecond. Building a tree there is extra complexity. Don't fix what isn't slow.

Simple rule: start with filter. Ask the profiler. If suggestions stutter on a long dictionary — then reach for a trie.

How to build the search box itself, with a delay and highlighting, is in "How to add search to your app".

Is a trie the same as a tree?

It's a special kind of tree. The twist is that the path from the root to a node is the key, letter by letter. The value isn't stored whole in a node — it's assembled along the way.

Why is a trie better than an object keyed by words?

An object { project: true } instantly answers "is this exact word here". But it can't answer "which words start with 'pro'" without scanning every key. A trie answers both.

Do letter case and lookalike letters get in the way?

They do: to a trie, "Pro", "pro" and "prо" with a Cyrillic "о" are three different branches. Normalize before inserting and searching: toLowerCase(), strip accents if needed, trim spaces.