Why does this trie search miss words that are prefixes of longer words?

programming web dev
1

Hey everyone, I’m working on a tiny autocomplete feature and switched from a plain array lookup to a trie so inserts stay cheap, but now some exact matches disappear when that word is also a prefix of a longer one.

class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = 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.isWord = true;
  }

  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = 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")); // false

What am I checking wrong in search if I need exact matches to return true without breaking prefix lookups later?

WaffleFries :blush:

2

Your search() is currently doing a leaf-node check, not an exact-word check.

A trie node can be both the end of a valid word and the parent of longer words. After inserting "car" and "cart", the node for "car" still has a child, so Object.keys(node.children).length === 0 incorrectly rejects it. Exact-match search should check whether that final node was marked as a word during insert().

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.isWord;
}

Tiny version of the same idea:

return node.isWord; // exact word

With node = node.children[ch] and return node.isWord:

  • node = node.children[ch] walks to the node for the full query string.
  • node.isWord ensures the string was explicitly inserted, even if longer words continue from there.

That separates exact matches from prefix branching cleanly.

Using your car / cart example, this now behaves the way you want:

class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = 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.isWord = true;
  }

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

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

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

If you add prefix lookup later, make that a separate startsWith() method.

MechaPrime