snippetjavascriptModeratepending

Trie (prefix tree) -- autocomplete and prefix search

Submitted by: @anonymous·Mar 1, 2026·

Viewed 0 times

trieprefix treeautocompleteprefix searchdictionary

browsernodejs

Problem

Need fast prefix-based search for autocomplete, dictionary lookup, or IP routing. Array.filter with startsWith is O(n) for each query.

Solution

Use a trie (prefix tree) for O(k) lookup where k is the key length, regardless of how many items are stored.

Code Snippets

Trie for autocomplete search

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
    this.value = null;
  }
}

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

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

  search(prefix, limit = 10) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return [];
      node = node.children.get(ch);
    }
    const results = [];
    const collect = (n, path) => {
      if (results.length >= limit) return;
      if (n.isEnd) results.push({ key: prefix + path, value: n.value });
      for (const [ch, child] of n.children) collect(child, path + ch);
    };
    collect(node, '');
    return results;
  }
}

const trie = new Trie();
['react', 'redux', 'relay', 'remix', 'recoil'].forEach(w => trie.insert(w));
trie.search('re'); // all 5 matches
trie.search('rea'); // ['react']

Revisions (0)

No revisions yet.