Trie (Prefix Tree)

How it works, step by step

1. 1

   Every node holds a map from letters to child nodes, plus one boolean flag. The root is an empty node: it spells the empty prefix.

2. 2

   Insert: walk down one letter at a time. If the child for that letter exists, step into it. If not, create it. This is why shared prefixes are stored only once.

3. 3

   After the last letter of an insert, set the word-end flag on the node you stand on. That flag is what makes "do" a real word instead of just the start of "dog".

4. 4

   Search: walk the same letters, but never create. A missing letter means the word cannot be there - stop at once.

5. 5

   Reached the last letter? Now check the flag. Letters alone only prove a prefix exists - that is exactly the question `startsWith` answers.

6. 6

   Every operation touches at most m nodes, where m is the length of the word. Ten words stored, or ten million - the walk is the same.

The code, in JavaScript

function createTrie() {
  // A node is just: children map + one flag. That flag IS the design.
  return { children: {}, isWord: false };
}

function insert(root, word) {
  let node = root;
  for (const ch of word) {
    // No child for this letter yet? Create it. Otherwise reuse it -
    // this line is why "car" and "card" share three nodes.
    node.children[ch] ??= createTrie();
    node = node.children[ch];
  }
  node.isWord = true;              // flag the END node - not the letters
}

function walk(root, letters) {
  let node = root;
  for (const ch of letters) {
    node = node.children[ch];
    if (node === undefined) return null;   // path breaks - stop early
  }
  return node;
}

function search(root, word) {
  const node = walk(root, word);
  return node !== null && node.isWord;   // letters exist AND flag is set
}

function startsWith(root, prefix) {
  return walk(root, prefix) !== null;    // letters exist - no flag needed
}

const trie = createTrie();
["cat", "car", "card", "dog", "do"].forEach((w) => insert(trie, w));

search(trie, "car");      // → true   (flag set on the 'r' node)
search(trie, "ca");       // → false  (nodes exist, flag missing)
startsWith(trie, "ca");   // → true   (a prefix is enough here)
search(trie, "cow");      // → false  (no 'o' under 'c')

Dry run: 5 inserts, then 3 searches

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• The word-end flag is the whole design. Without it, "do" and "dog" are indistinguishable - and a search that forgets the flag check is just `startsWith` with a misleading name.
• Fixed 26-slot child arrays explode memory: every node pays for 26 pointers even when it has one child. Use an object or `Map` unless the alphabet is truly small and dense.
• A trie beats a hash map only for prefix questions. For exact lookup a hash touches the word once; the trie chases one pointer per letter and loses on cache misses.
• Deleting a word must not delete shared nodes: removing "car" has to keep 'c'-'a'-'r' alive while "card" still needs them. Refcount each node (the Count + delete tab) or prune only child-less, unflagged nodes.

Trie (Prefix Tree) vs. its closest relatives