Introduction

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.

Build a Trie

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">Add words and watch the <b>trie</b> grow. Words that share a beginning share the same branch &mdash; only where they differ does the path split. Then type a prefix and autocomplete walks just those letters.</p>
<div class="row">
  <input id="word" type="text" placeholder="add a word, e.g. card" maxlength="12" autocomplete="off" />
  <button id="add" type="button">Add word</button>
  <button id="seed" type="button" class="ghost">Sample words</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>
<div class="row">
  <input id="prefix" type="text" placeholder="autocomplete a prefix, e.g. car" maxlength="12" autocomplete="off" />
</div>
<div class="status" id="status">Add a word to start building the trie.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A trie: each node has children keyed by a single letter. Inserting a word walks its letters, creating nodes only where they are missing, so words that share a prefix share the same path. Lookup/autocomplete follows the query's letters (O(m), independent of how many words are stored).
const ROOT = () => ({ ch: {}, end: false });
let root = ROOT();
const words = new Set();

function insert(w){
  let node = root;
  for(const c of w){ if(!node.ch[c]) node.ch[c] = ROOT(); node = node.ch[c]; }
  node.end = true; words.add(w);
}
// Walk a prefix; return the node it ends at, or null if the path breaks.
function walk(p){ let node = root; for(const c of p){ if(!node.ch[c]) return null; node = node.ch[c]; } return node; }
// Collect all complete words under a node (depth-first).
function collect(node, pre, out){ if(node.end) out.push(pre);
  for(const c of Object.keys(node.ch).sort()) collect(node.ch[c], pre+c, out); return out; }

const setStatus = (t, cls='') => { const s = document.getElementById('status'); s.textContent = t; s.className = 'status '+cls; };

// ── Layout: assign x by a left-to-right walk of leaves, y by depth. ──
function layout(){
  const nodes = [], edges = []; let leafX = 0;
  (function place(node, depth, letter, parent){
    const id = nodes.length;
    const rec = { id, depth, letter, end: node.end, x: 0, hot: false };
    nodes.push(rec);
    const kids = Object.keys(node.ch).sort();
    if(kids.length === 0){ rec.x = leafX++; }
    else {
      const childIds = [];
      for(const c of kids){ const cid = place(node.ch[c], depth+1, c, id); childIds.push(cid); edges.push({ from: id, to: cid }); }
      rec.x = (nodes[childIds[0]].x + nodes[childIds[childIds.length-1]].x) / 2;
    }
    return id;
  })(root, 0, '', -1);
  return { nodes, edges, span: Math.max(1, leafX) };
}

function render(hotPrefix){
  const svg = document.getElementById('tree'); svg.innerHTML = '';
  const { nodes, edges, span } = layout();
  const W = 600, H = 360, padX = 36, padY = 36;
  const maxDepth = Math.max(1, ...nodes.map(n => n.depth));
  const rowH = (H - 2*padY) / maxDepth;
  const X = n => padX + (n.x + 0.5) * ((W - 2*padX) / span);
  const Y = n => padY + n.depth * rowH;

  // Give every node its accumulated string. layout() builds `nodes` in the same pre-order DFS (children sorted) as this walk, so the i-th string lines up.
  const order = []; (function dfs(node, acc){ order.push(acc);
    for(const c of Object.keys(node.ch).sort()) dfs(node.ch[c], acc+c); })(root, '');
  nodes.forEach((n, i) => n.acc = order[i]);

  // A node is "hot" when its letters are a prefix of what the user typed AND the whole typed prefix actually exists in the trie — that highlights the walked path.
  const valid = !!hotPrefix && !!walk(hotPrefix);
  nodes.forEach(n => { n.hot = valid && hotPrefix.startsWith(n.acc); });

  const ns = 'http://www.w3.org/2000/svg';
  // edges
  edges.forEach(e => {
    const a = nodes[e.from], b = nodes[e.to];
    const line = document.createElementNS(ns, 'line');
    line.setAttribute('x1', X(a)); line.setAttribute('y1', Y(a));
    line.setAttribute('x2', X(b)); line.setAttribute('y2', Y(b));
    line.setAttribute('class', 'edge' + (a.hot && b.hot ? ' hot' : ''));
    svg.appendChild(line);
  });
  // nodes
  nodes.forEach(n => {
    const g = document.createElementNS(ns, 'g');
    g.setAttribute('class', 'node' + (n.end ? ' word' : '') + (n.hot ? ' hot' : ''));
    const c = document.createElementNS(ns, 'circle');
    c.setAttribute('cx', X(n)); c.setAttribute('cy', Y(n)); c.setAttribute('r', n.depth === 0 ? 11 : 14);
    g.appendChild(c);
    const t = document.createElementNS(ns, 'text');
    t.setAttribute('x', X(n)); t.setAttribute('y', Y(n));
    t.textContent = n.depth === 0 ? '•' : n.letter;
    g.appendChild(t);
    svg.appendChild(g);
  });
}

function addWord(){
  const inp = document.getElementById('word'); const w = (inp.value || '').trim().toLowerCase().replace(/[^a-z]/g,'');
  if(!w){ setStatus('Type a word made of letters.', 'bad'); return; }
  const had = words.has(w); insert(w); inp.value = '';
  render(document.getElementById('prefix').value.trim().toLowerCase());
  setStatus(had ? fmt('"%w%" was already in the trie (%size% words).', { w: w, size: words.size }) : fmt('Inserted "%w%" in %length% steps. Trie now holds %size% words.', { w: w, length: w.length, size: words.size }), 'ok');
}
function autocomplete(){
  const p = document.getElementById('prefix').value.trim().toLowerCase();
  render(p);
  if(!p){ setStatus(words.size ? fmt('Showing the full trie ( %size% words).', { size: words.size }) : 'Add a word to start building the trie.'); return; }
  const node = walk(p);
  if(!node){ setStatus(fmt('"%p%" — no word starts with that prefix.', { p: p }), 'bad'); return; }
  const found = collect(node, p, []);
  setStatus(fmt('Walked %length% letters → %length2% match%v%: %found%', { length: p.length, length2: found.length, v: found.length===1?'':'es', found: found.join(', ') }), 'ok');
  console.log(fmt('autocomplete result for "%p%":', { p: p }), found, fmt('| steps to reach prefix node: %length%', { length: p.length }));
}

document.getElementById('add').addEventListener('click', addWord);
document.getElementById('word').addEventListener('keydown', e => { if(e.key === 'Enter') addWord(); });
document.getElementById('prefix').addEventListener('input', autocomplete);
document.getElementById('reset').addEventListener('click', () => { root = ROOT(); words.clear(); document.getElementById('prefix').value=''; render(''); setStatus('Cleared. Add a word to start building the trie.'); });
document.getElementById('seed').addEventListener('click', () => {
  ['car','card','care','cart','dog','dot','do'].forEach(insert);
  render(document.getElementById('prefix').value.trim().toLowerCase());
  setStatus('Added sample words. Notice car/card/care/cart share the "c-a-r" road.', 'ok');
});
render('');
Result
Console

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.

The Real Complexity

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

  • Trie lookup is O(m)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)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)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)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/tries-suffix/Content licensed under CC BY-NC 4.0.