Cairn
data structures · prefix tree · O(k) insert/search/delete, k = word length

↩ 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.

Loaded with cat, car, card, care, cop, do, dog, dot. Try Prefix with "ca", then Delete "do" and watch dog/dot stay reachable.

Core operations

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 — and even then, less than "dense" suggests. 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 for search, measured below, but not necessarily for insert, where allocating and zero-filling a fixed-size array for every new node has its own real cost. 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 — measured as high as 64× more pointer slots allocated than actually used; the map trades a small constant lookup cost for space proportional to the branching that's actually present. See Measuring array nodes vs. map nodes below for the exact numbers in both a best-case-dense and a realistic-sparse scenario, including a wrinkle even the dense case doesn't escape: most of any trie's nodes are leaves with zero children, and a leaf still allocates — and wastes — its entire array. This is the same "only pay for what's used" trade the hash table page's separate-chaining buckets make, one level down.

Measuring array nodes vs. map nodes

The Pitfall above says a fixed-size array per node wastes space unless the alphabet is small and dense, and is "genuinely faster" when it is. Both halves are true in direction, but neither is as clean as that phrasing suggests. This measures the exact shipped Trie class above (Map-keyed children) against an array-backed sibling with the same insert/ search API, correctness cross-checked against each other first, on two scenarios: dense — every 3-letter string over the full 26-letter alphabet, the textbook best case for the array, full branching at every internal node — and sparse — 20,000 random 10-character strings over a 64-character alphabet (letters, digits, and two symbols), the "arbitrary byte strings" case the Pitfall names.

Click either button — each builds a fresh Map-based trie and an array-based trie over the same words, cross-checks every lookup between them, times insert and search, and counts how many of the array's allocated child slots actually hold a node.

Repeated runs (median of several timed trials each, as the widget above does) settled into a consistent shape in testing. Dense: the array wins search by roughly 1.6×–2.5×, but insert only by a much smaller, noisier 1.1×–1.5× — and even here, only 703 of the trie's 18,279 nodes are internal (1 + 26 + 26², exact by construction); every one of the remaining leaves still allocates a full 26-slot array it never fills, so overall slot utilization lands at roughly 3.8%, nowhere near the near-100% "small and dense" might suggest. Sparse: the array's insert advantage flips entirely — the map is roughly 2.4×–2.9× faster to build, because allocating and zero-filling a 64-slot array for every new node (most of which end up with exactly one child) costs more than the map's lazy per-entry allocation. The array still wins search even here, by roughly 1.2×–1.4× — a populated slot is a populated slot, direct indexing doesn't care how many of its 64 siblings are empty. Memory tells the clearest story: only ~1.56% of the array's allocated child-pointer slots are ever used, meaning it holds roughly 64× more pointer-sized slots than it has real children. "Small and dense" buys the array a real, repeatable win on search in both scenarios tested — but "genuinely faster" undersells that the win is search specifically, not insert, and "wastes space" turns out to apply even to the dense case, just far less severely than the sparse one.

Where tries show up

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.