patternjavascriptModerate

Trie enables O(k) prefix lookups and autocomplete where k is key length

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

trieprefix treeautocompleteprefix searchradix treeword lookup

Problem

Implementing autocomplete or prefix search with a Set/Map of strings requires scanning all entries — O(n*k). A trie enables O(k) lookup and prefix queries regardless of dictionary size.

Solution

Build a trie with nodes containing a children Map and an isEnd flag. Insert by walking/creating nodes per character. Search prefix by walking nodes. Collect completions with DFS from the prefix endpoint.

Why

A trie exploits the shared prefix structure of strings. All words starting with 'app' share the root-a-p-p path. Lookup is bounded by key length, not dictionary size.

Gotchas

Memory usage can be high — each node has up to 26 children for ASCII. Consider compressed tries (radix tree) for large dictionaries
Case sensitivity: normalize to lowercase before insert and search
DFS for completions can be expensive if the prefix has millions of completions — add a limit parameter

Code Snippets

Trie with prefix autocomplete

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

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

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

  startsWith(prefix) {
    let node = this.root;
    for (const c of prefix) {
      if (!node.children.has(c)) return [];
      node = node.children.get(c);
    }
    const results = [];
    const dfs = (n, buf) => {
      if (n.isEnd) results.push(buf);
      for (const [c, child] of n.children) dfs(child, buf + c);
    };
    dfs(node, prefix);
    return results;
  }
}

Context

Autocomplete, spell checking, prefix-based search, or IP routing tables

Revisions (0)

No revisions yet.