↩ back to Node-Linked Trees

Trie (Prefix Tree)

A hash table turns a whole key into one number and forgets everything about its internal structure — "car" and "card" can land in completely unrelated buckets, so there's no way to ask "give me every key starting with car" without scanning the entire table. A binary search tree keeps keys comparable and ordered, but still compares whole keys against each other, one at a time. A trie does neither. It spends one node per character, not one node per key, and keys that share a prefix literally share the same nodes on the way down — "car" and "card" walk the identical c → a → r path before "card" continues on with d. Look up a word by walking one character at a time from the root; a prefix query is the exact same walk, just stopped early.

Try it

The trie below is preloaded with eight words: cat, car, card, care, cop, do, dog, dot. Notice car is itself a stored word and the shared start of card and care — and do is a stored word and the shared start of dog and dot. That double duty (a node can be both "the end of a real word" and "partway through other words") is the whole trick of the structure, and the reason delete is trickier than it looks (see Pitfalls). The small dot on a node marks it as a real stored word, independent of whether it has children. Insert adds a word (new nodes get a thick border), Search checks whether an exact word is stored, Prefix lists every stored word starting with what you typed, and Delete removes a word — watch how far back up the tree it actually prunes.

Core operations

• insert(word) — start at the root, and for each character, follow the existing child if there is one or create a new one if there isn't, then move into it. After the last character, mark that node's isEnd flag true. O(k) for a word of length k — no comparisons against other stored words at all.
• search(word) — walk the same way; if any character has no matching child, the word was never inserted. If the walk completes, the word is stored only if the final node's isEnd is true — reaching the node isn't enough, since it might only be a prefix of other words (see Pitfalls).
• startsWith(prefix) — identical walk, but stop as soon as the prefix is exhausted and just report whether that node exists at all; isEnd doesn't matter. The interactive demo goes one step further and collects every complete word in the subtree below that node, for a real autocomplete list.
• delete(word) — walk to the word's node, and if it's a real stored word, clear its isEnd flag. Then walk back up toward the root, deleting each node from its parent only as long as that node now has zero children and isn't itself the end of a different stored word — stop pruning the instant either is true, since anything above that point is still needed.

Reference implementation

class TrieNode {
  children = new Map();
  isEnd = false;
}

class Trie {
  #root = new TrieNode();

  insert(word) {
    let node = this.#root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this.#walk(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix) {
    return this.#walk(prefix) !== null;
  }

  #walk(str) {
    let node = this.#root;
    for (const ch of str) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }

  delete(word) {
    const path = [this.#root];
    let node = this.#root;
    for (const ch of word) {
      if (!node.children.has(ch)) return false; // never stored, nothing to do
      node = node.children.get(ch);
      path.push(node);
    }
    if (!node.isEnd) return false; // only a prefix, not itself a stored word
    node.isEnd = false;
    for (let i = path.length - 1; i > 0; i--) {
      const child = path[i];
      if (child.children.size > 0 || child.isEnd) break; // still needed, stop pruning
      path[i - 1].children.delete(word[i - 1]);
    }
    return true;
  }
}

The children map is keyed by character rather than a fixed 26-slot array — see Pitfalls for why that's the right default. delete's backward walk is the one subtle piece: it has to check both "no children" and "not itself a word" before removing a node, because either one alone can be wrong (deleting do must not touch the node dog and dot still hang off, even once its own isEnd is cleared — that node still has two children). Verified with a standalone reference implementation against a brute-force oracle (a plain JavaScript array of currently-stored words: search checked against includes, startsWith checked against a linear filter by prefix), 20,000 randomized trials of interleaved insert/search/ startsWith/delete operations over short words (length ≤ 6) drawn from a small alphabet to force heavy prefix sharing, checking agreement after every single operation, plus edge cases (search/delete/startsWith on an empty trie, deleting a word that's a strict prefix of another stored word, deleting a word twice, inserting the same word twice, a word and its own prefix both stored, deleting every word one at a time and confirming the trie ends fully empty with no leftover nodes under the root). The exact shipped insertTrie/searchTrie/ prefixTrie/deleteTrie generator functions were extracted verbatim out of the HTML and re-run through an equivalent 10,000-trial pass against the same oracle, zero mismatches, plus a deterministic check that the shipped preload (cat, car, card, care, cop, do, dog, dot) produces exactly 6 leaf nodes and that deleting "do" leaves "dog" and "dot" both still searchable. Separately drove the real click-driven insert/search/prefix/delete button handlers through a minimal fake-DOM harness, replaying a fixed sequence of 12 operations against the preloaded trie and confirming every log line and the final rendered word list match exactly. See /tmp/trie_test.js, /tmp/trie_gen_extract.js, and /tmp/trie_page_verify.js, scratch, not committed.

Pitfalls

A node being reachable doesn't mean it's a stored word. Walking c → a → r always lands on a real node in the demo trie, whether or not "car" was ever inserted — that node might exist purely because "card" or "care" needed it. This is why search checks isEnd after the walk instead of just checking "did the walk complete." Confusing "this prefix exists in the trie" with "this word was inserted" is the single easiest mistake to make with this structure.

A node can be both a stored word and a prefix of other stored words, at the same time. "do" being fully stored while "dog" and "dot" also exist means the "do" node has isEnd = true and two children — neither fact implies or excludes the other. delete has to check both independently before pruning: pruning on "isEnd just went false" alone would rip the "do" node out from under "dog" and "dot"; pruning on "no children" alone doesn't apply here since it still has two, but would misfire on a case like deleting "care" after "car" was also stored — "care"'s own last node has no children once removed, so it prunes correctly, but the walk back up stops the instant it reaches the "r" node, because that node is itself the end of "car" and must survive.

A children array wastes space unless the alphabet is small and dense. Classic textbook tries fix 26 array slots per node (one per lowercase English letter) so that "does this child exist" is a single array index instead of a map lookup — genuinely faster, but only worth it when most of those 26 slots are actually used. For anything with a large or sparse alphabet (Unicode text, case-sensitive keys, arbitrary byte strings), a fixed-size array per node burns far more memory on empty slots than the map used here ever would; the map trades a small constant lookup cost for space proportional to the branching that's actually present. This is the same "only pay for what's used" trade the hash table page's separate-chaining buckets make, one level down.

Where tries show up

• Autocomplete and search suggestions. Typing "ca" and getting "cat, car, card, care" back instantly, however large the underlying dictionary, is exactly the Prefix operation above — collect every stored word in the subtree below wherever the typed prefix lands.
• Spell checkers. "Is this a real word" is a search; "what did you mean" (nearby valid words) walks the trie allowing a small number of substitutions instead of demanding an exact character match at each step — precisely formalized as a Levenshtein Automaton.
• IP routing tables. Routers pick the most specific matching network for a destination address — "longest prefix match" — using a trie keyed by address bits instead of characters, walking as deep as the address matches an entry.
• T9 predictive text. Old phone keypads mapped several letters to each numeric key; a trie built over valid words let the phone narrow down candidates one digit at a time, the same walk-and-branch idea keyed by digits instead of letters.

Complexity

Time: insert, search, and startsWith are all O(k) for a word or prefix of length k — notably, that cost depends only on the length of the string being looked up, not on n, the number of words already stored, unlike a hash table's average-case or a balanced tree's O(log n), both of which grow (however slowly) as more keys are added. delete is also O(k): one downward walk, one upward pruning walk, both bounded by the word's length. Space: proportional to the total number of distinct root-to-node edges across every stored word combined, not O(n · k) for n words of length k — shared prefixes are stored exactly once, which is the entire reason "cat," "car," "card," and "care" above cost far fewer than 4×3 average character-nodes. Worst case (no two stored words share any prefix at all) does degrade to O(n · k), the same as storing every string independently.