What Is a Trie (Prefix Tree)?

A trie (prefix tree) stores strings character by character along tree paths, so all words sharing a prefix share the same path. It makes prefix searches and autocomplete fast, independent of how many words are stored.

The concept

Each node represents a character; a flag marks where a word ends. Looking up a word of length m takes O(m).

Tries power autocomplete, spell checkers and IP routing. They use more memory than hash sets but answer 'all words starting with…' efficiently.

Words: car, cat, dog

Practical examples

Insert and search

class Trie {
  root = {}
  insert(w) { let n = this.root; for (const c of w) n = n[c] ??= {}; n.$ = true }
  has(w) { let n = this.root; for (const c of w) { n = n[c]; if (!n) return false } return !!n.$ }
}

Autocomplete

function complete(trie, prefix) {
  let n = trie.root
  for (const c of prefix) { n = n[c]; if (!n) return [] }
  const out = []
  const walk = (node, s) => { if (node.$) out.push(s); for (const k in node) if (k !== '$') walk(node[k], s + k) }
  walk(n, prefix); return out
}

Common mistakes

• Using a trie for tiny word lists.
• Not handling case or Unicode normalisation.
• Ignoring memory use on large alphabets.

Key takeaways

• Shared prefixes share paths.
• O(word length) lookups.
• Ideal for autocomplete.

FAQ

Trie vs hash set?

Hash sets test membership; tries also answer prefix queries.

What is a radix tree?

A compressed trie that merges single-child chains.