Tries & Suffix Trees

Type "comp" into a search box and, before you finish the word, a list appears: computer, complexity, complete, compress. The machine just sifted a dictionary of perhaps a million entries — and it did it faster than you could blink. How?

The trick is an old, elegant data structure called a trie (from retrieval, usually said "try"). Instead of storing each word as a separate string, a trie stores words letter by letter along shared paths. Every word that begins with "comp" walks the same first four steps; only where the words differ does the path branch.

That single idea — let common prefixes share one road — is why looking something up costs time proportional to the length of your query, not the size of the collection. This is not an open problem or a deep mystery. It is one of computer science's quietly solved wins, and once you see it you spot tries everywhere.

Add a few words below and watch the trie grow. Words that share a beginning share the same branch — "car", "card" and "care" all walk the same "c-a-r" road before splitting. Then type a prefix to autocomplete: the trie jumps straight to that node and lists everything underneath it.

<p class="hint">{{hint}}</p>
<div class="row">
  <input id="word" type="text" placeholder="{{ph_word}}" maxlength="12" autocomplete="off" />
  <button id="add" type="button">{{btn_add}}</button>
  <button id="seed" type="button" class="ghost">{{btn_seed}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div class="row">
  <input id="prefix" type="text" placeholder="{{ph_prefix}}" maxlength="12" autocomplete="off" />
</div>
<div class="status" id="status">{{status_init}}</div>
<svg id="tree" viewBox="0 0 600 360" preserveAspectRatio="xMidYMid meet"></svg>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0; }
input { font: 500 14px system-ui, sans-serif; padding: .45rem .6rem; border: 1px solid #adb1b8;
        border-radius: 8px; flex: 1 1 160px; min-width: 120px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
#tree { width: 100%; height: auto; background: #f6f8fa; border: 1px solid #e3e8ee; border-radius: 10px; }
.edge { stroke: #adb1b8; stroke-width: 2; }
.edge.hot { stroke: #e63946; stroke-width: 3; }
.node circle { fill: #e8eef3; stroke: #cdd9e3; stroke-width: 2; }
.node.word circle { fill: #1d3557; stroke: #1d3557; }
.node.hot circle { fill: #e63946; stroke: #c92f3c; }
.node text { font: 700 14px ui-monospace, monospace; fill: #1d3557; text-anchor: middle; dominant-baseline: central; }
.node.word text, .node.hot text { fill: #fff; }

// Code not found

Notice what doesn't happen: adding the 100th word does not slow down the search. A lookup only follows the letters you typed, so its cost depends on your word, never on how many words are stored. That is the whole magic — and it is exactly the opposite of the brute-force scan that compares your query against every entry one by one.

How hard is searching text, really? For these structures the answer is wonderfully tame — this is a solved problem.

• Trie lookup is $O(m)$, where m is the length of the word you are searching for. Crucially, it does not depend on n, the number of words stored. A million-word dictionary and a ten-word list answer a 6-letter query in the same handful of steps.
• Insertion is also $O(m)$ — you just walk the word's letters, creating nodes where they are missing.
• Autocomplete (prefix search) walks the p letters of the prefix, then collects the words in that subtree — you touch only the relevant branch, never the rest of the dictionary.
• Suffix trees go further. A suffix tree packs every suffix of a text into one trie, so it can answer "does this pattern occur?" in $O(m)$ time and find all occurrences quickly. Peter Weiner introduced them in 1973; Esko Ukkonen gave a famously clean linear-time construction in 1995. Building the index over a length-n text takes only $O(n)$ time.

The trade is space for speed: a trie can use a lot of memory, and engineers compress it (radix/PATRICIA tries, suffix arrays) to tame that. But there is no looming impossibility here — unlike P vs NP, text search is a corner of the field that was understood and optimized decades ago.

You meet tries and suffix trees dozens of times a day without noticing:

• Autocomplete and search suggestions: every keystroke walks one branch of a trie to surface matching words instantly.
• Spell-checkers and dictionaries: a trie stores a whole language compactly and checks membership in the time it takes to spell the word.
• IP routing: routers use compressed tries to match the longest-matching network prefix of a destination address at line speed.
• Bioinformatics: suffix trees and suffix arrays let you scan billions of DNA bases for a pattern, a building block of genome assembly and alignment.
• Full-text and substring search: suffix structures power "find every place this phrase appears" across huge documents.

The common thread is the same as in pattern matching: pre-organize the text once so that each later query only does work proportional to the query itself.

A trie takes a pile of words and finds the structure already hidden in them: shared beginnings. By letting common prefixes share one road, it makes lookup cost depend on your word, not on the dictionary — and suffix trees push the same idea to every substring, indexed in linear time.

This is computer science at its most satisfying: a clean idea, proven fast, and solved for good. The next time autocomplete reads your mind after three letters, you'll know it isn't magic — it's just a tree of letters, walked exactly as far as you typed. And when a problem can't be tamed this neatly, that's where the harder questions like P vs NP begin.