Why does this trie search say a missing word exists after deletes?

programming web dev
1

Hey folks, I’m working on a tiny autocomplete trie in JavaScript for a side project, and I’m trying to support deletes without rebuilding the whole thing. Search is fast, but after removing one word I sometimes still get true for a word that should be gone, which feels worse than being a little slower.

class TrieNode {
  constructor() {
    this.children = {};
    this.end = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.end = true;
  }

  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return true;
  }

  delete(word, node = this.root, i = 0) {
    if (i === word.length) {
      node.end = false;
      return Object.keys(node.children).length === 0;
    }

    const ch = word[i];
    if (!node.children[ch]) return false;

    const shouldDeleteChild = this.delete(word, node.children[ch], i + 1);
    if (shouldDeleteChild) delete node.children[ch];

    return Object.keys(node.children).length === 0;
  }
}

const trie = new Trie();
trie.insert("car");
trie.insert("cart");
trie.delete("cart");
console.log(trie.search("cart"));

What am I missing in the delete/search logic so removing a word does not leave ghost matches behind?

Yoshiii

2

Your search(word) is currently doing path existence, not full-word existence.

A trie node can exist because it is part of some longer word, even when the current word was deleted. That means walking the characters successfully is not enough by itself. The actual stored-word check is the end flag on the last node.

The smallest fix is this:

search(word) {
  let node = this.root;
  for (const ch of word) {
    if (!node.children[ch]) return false;
    node = node.children[ch];
  }
  return node.end;
}

Tiny version of the same point:

"car" path exists !== "car" is stored

With return node.end and node.end = false working together, the behavior lines up:

  • return node.end does the full-word check at the final node.
  • node.end = false ensures delete("cart") removes the word marker without breaking shared nodes like c -> a -> r.

So "car" can stay valid while "cart" becomes false.

Using your insert("car"), insert("cart"), and delete("cart") flow, it should behave like this:

class TrieNode {
  constructor() {
    this.children = {};
    this.end = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.end = true;
  }

  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.end;
  }

  delete(word, node = this.root, i = 0) {
    if (i === word.length) {
      node.end = false;
      return Object.keys(node.children).length === 0;
    }

    const ch = word[i];
    if (!node.children[ch]) return false;

    const shouldDeleteChild = this.delete(word, node.children[ch], i + 1);
    if (shouldDeleteChild) delete node.children[ch];

    return Object.keys(node.children).length === 0;
  }
}

const trie = new Trie();
trie.insert("car");
trie.insert("cart");

console.log(trie.search("car"));  // true
console.log(trie.search("cart")); // true

trie.delete("cart");

console.log(trie.search("cart")); // false
console.log(trie.search("car"));  // true

One practical tip: your delete cleanup return should usually also consider node.end, so you do not prune a node that still ends another word.

Ellen

3

@Ellen1979 already called out return node.end, and the other sharp edge is your cleanup line should be return !node.end && Object.keys(node.children).length === 0 or deleting "car" can accidentally prune the shared r node that "cart" still needs.

Sarah :blush:

Sarah

4

@sarah_connor Yep — the !node.end check is the key fix, because it stops delete from pruning the shared r node that cart still still needs. And for the false positive on search, search() should return node.end, not just whether traversal succeeded.

Arthur

5

@ArthurDent your shared r example is the right edge case, and the other one is deleting a word that was never inserted because bubbling up plain false mixes up “not found” with “don’t prune” and can hide cleanup bugs later.

Hari