Building Fast Autocomplete Search with a Prefix Trie in JavaScript

Searching through an array of 50,000 words on every keystroke in an autocomplete search box using array.filter(w => w.startsWith(query)) yields unacceptable input lag. Each keystroke iterates through every word in the dictionary, creating (O(N imes L)) latency.

A Trie (Prefix Tree) organizes characters into an associative tree structure where search time depends strictly on the length of the query prefix (O(L)), completely independent of the total dictionary size (N).

Example #

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

Implementation #

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

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

  searchPrefix(prefix) {
    let node = this.root;
    for (const char of prefix.toLowerCase()) {
      if (!node.children[char]) return [];
      node = node.children[char];
    }
    return this._collectWords(node, prefix);
  }

  _collectWords(node, prefix) {
    const results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (const [char, childNode] of Object.entries(node.children)) {
      results.push(...this._collectWords(childNode, prefix + char));
    }
    return results;
  }
}

Main Point: A Prefix Trie provides instantaneous autocomplete suggestions in (O(L)) time, scaling effortlessly across large dictionaries.

Credits #

Photo by Aaron Burden on Unsplash

← Home