Autocomplete Like a Boss: Building Tries Inspired by The Matrix

The Quest Begins (The "Why")

I still remember the first time I tried to build a search‑suggest box for a side project. I had a list of 200 000 product names, and every keystroke triggered a full scan:

function suggest(prefix, words) {
  return words.filter(w => w.startsWith(prefix));
}

The UI felt like wading through molasses—each letter typed added a noticeable lag, and with a bigger dataset the page would freeze. I kept thinking, there has to be a smarter way. That frustration was the dragon I needed to slay, and the treasure I was after was a data structure that could give me instant prefix look‑ups without scanning the whole collection every time.

The Revelation (The Insight)

The answer arrived in the form of a trie (pronounced “try”), sometimes called a prefix tree. Imagine each word as a path from the root to a leaf, where every edge represents a single character. All words that share a prefix share the same initial path.

Why does this work so well?

• Shared work is done once. Instead of comparing the prefix against every word, we walk down the trie following the characters of the prefix. The moment we run out of characters, we’re standing exactly at the node that represents all words with that prefix.
• Lookup cost depends only on the prefix length, not on the total number of stored words. If the prefix is cat, we make three moves—c → a → t—regardless of whether we have ten or ten‑million words.

That realization felt like pulling off a perfect combo in Street Fighter: crisp, decisive, and instantly rewarding.

Wielding the Power (Code & Examples)

The Struggle: Naïve Filtering

Before the trie, my autocomplete looked like this (the “before” code):

// words is an array of strings
function autocompleteNaive(prefix, words) {
  const lower = prefix.toLowerCase();
  return words.filter(word => word.toLowerCase().startsWith(lower));
}

Problems:

• O(N · L) time per query, where N is the number of words and L the average word length (because startsWith scans each word).
• No reuse of work across queries—each keystroke starts from scratch.

The Victory: Building a Trie

Now let’s build the trie from scratch. Each node stores a map of children and a flag that tells us if a word ends there.

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

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

  // Insert a word – O(word length)
  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch);
    }
    node.isEnd = true;
  }

  // Find the node that represents the prefix – O(prefix length)
  _findNode(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return null; // prefix not present
      node = node.children.get(ch);
    }
    return node;
  }

  // Return all words with given prefix – O(prefix length + output size)
  suggest(prefix) {
    const node = this._findNode(prefix);
    if (!node) return []; // no matches

    const results = [];
    const dfs = (curr, path) => {
      if (curr.isEnd) results.push(path);
      for (const [ch, child] of curr.children) {
        dfs(child, path + ch);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

Why this is fast:

• Building the trie costs O(total characters) across all words—we visit each character exactly once.
• A query walks down the trie following the prefix (O(|prefix|)) and then does a DFS only through the subtree that matches that prefix. The DFS work is proportional to the number of characters in the output, which is unavoidable if we have to return those words.

Using It

const dictionary = ["car", "cart", "carbon", "cat", "cater", "dog", "dot"];
const trie = new Trie();
for (const w of dictionary) trie.insert(w);

console.log(trie.suggest("ca")); // ["car", "cart", "carbon", "cat", "cater"]
console.log(trie.suggest("do")); // ["dog", "dot"]
console.log(trie.suggest("z"));  // []   (quick miss)

Traps to Avoid (the “gotchas” on the quest)

1. Forgetting the end‑of‑word flag. If you never set isEnd = true, the trie can tell you that a prefix exists but won’t know whether a complete word ends there, causing false positives.
2. Case‑sensitivity mix‑ups. I once inserted words in lowercase but queried with the original casing, yielding empty results. Normalize both sides (or store both) to keep things predictable.
3. Memory blow‑up with huge alphabets. For Unicode or very large character sets, a Map is fine; a fixed‑size array would waste space. Choose the structure that matches your alphabet size.

Why This New Power Matters

With a trie in your toolbox, autocomplete goes from a laggy afterthought to a snappy, responsive feature that users actually enjoy. You can now:

• Power real‑time search bars on e‑commerce sites without hammering the database.
• Build command‑line helpers that suggest flags or arguments as you type.
• Implement IP‑address routing tables (the classic networking use‑case) where longest‑prefix match is essential.

The best part? The concept scales. Insert a million words, and a ten‑character prefix still costs only ten steps to locate—then you just walk the matching subtree.

Your Turn

Here’s a challenge: grab a list of your favorite movie titles (or video‑game names, or anything you love), load them into a trie, and build a tiny autocomplete widget that suggests titles as you type. Play with the DFS to return results sorted by popularity or length, and see how fast it feels compared to the naive filter.

Drop a link to your demo in the comments—I can’t wait to see what you build!

---

Happy coding, and may your prefixes always be short and your suggestions swift!