The Force Awakens Your Autocomplete: Building a Trie from Scratch

The Quest Begins (The "Why")

Honestly, I was stuck on a take‑home assignment that asked for a “search‑as‑you‑type” widget. My first instinct? Throw every product name into an array and filter it on each keystroke. It worked… until the list hit 10 k items. The UI froze, the user stared at a spinning loader, and I felt like I’d just walked into a boss fight with a wooden sword.

That moment made me ask: Is there a smarter way to store words so that fetching all matches for a prefix is instant? The answer turned out to be a data structure I’d only seen in textbooks: the Trie.

The Revelation (The Insight)

A Trie (pronounced “try”) is basically a tree where each node represents a single character. Instead of storing whole strings in a flat list, we break every word into its letters and link them together. The magic lies in two simple facts:

1. Prefix sharing – Words that start with the same letters share the same path from the root.
2. Terminal flag – A node marks the end of a word, so we know when a complete suggestion lives at that point.

Because of (1), searching for a prefix means we just walk down the tree following the characters of that prefix. Once we arrive at the node that represents the prefix, every word underneath it is a valid autocomplete result. No scanning, no regex, no wasted comparisons.

Why does this give us O(L) insertion and O(P + k) query?

• Inserting a word of length L touches exactly L nodes – one per character – so it’s linear in the word size.
• To answer a query, we first walk P steps to reach the prefix node (P = prefix length). Then we perform a depth‑first search to collect all k words beneath it. The work is proportional to the prefix length plus the number of results we actually return. In the worst case, k could be large, but we’re only doing work proportional to the output size – optimal for autocomplete.

That insight felt like finding a hidden shortcut in a maze. Suddenly, the “brute force filter” approach looked like using a spoon to dig a tunnel.

Wielding the Power (Code & Examples)

The struggle: naive filtering

// Before – O(N * L) per keystroke, where N = number of words
const dictionary = ['apple', 'app', 'application', 'banana', 'band', 'bandana'];

function naiveAutocomplete(prefix) {
  return dictionary.filter(word => word.startsWith(prefix));
}

// Example
console.log(nautocomplete('app')); // ['apple', 'app', 'application']

If dictionary grows to hundreds of thousands, each keystroke becomes a noticeable lag.

The victory: a Trie class

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

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

  // Insert a word – O(L)
  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;
  }

  // Helper: collect all words from a given node
  *collectWords(node, prefix) {
    if (node.isEnd) yield prefix;
    for (const [ch, child] of node.children) {
      yield* this.collectWords(child, prefix + ch);
    }
  }

  // Return all words that start with prefix – O(P + k)
  *autocomplete(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) {
        // No words with this prefix
        return;
      }
      node = node.children.get(ch);
    }
    yield* this.collectWords(node, prefix);
  }
}

// Usage
const trie = new Trie();
['apple', 'app', 'application', 'banana', 'band', 'bandana'].forEach(w => trie.insert(w));

console.log([...trie.autocomplete('app')]); // ['app', 'apple', 'application']
console.log([...trie.autocomplete('ban')]); // ['banana', 'band', 'bandana']

Common traps I fell into:

• Forgetting to set isEnd = true – then "app" would never appear as a suggestion even though it’s a valid word.
• Using a plain object for children and accidentally hitting prototype properties (__proto__, constructor). A Map avoids that headache.
• Not making the collector a generator (function* or yield*). Returning an array forces us to allocate space for all results before we can yield them, which defeats the purpose of streaming suggestions in a UI.

Interview‑style problems

1. Design a search suggest box – Given a list of product names, return the top k matches for a user’s typed prefix.
   
   Solution: Build a Trie, insert all product names, then on each keystroke walk to the prefix node and perform a limited depth‑first search that stops after k results.

2. Longest common prefix among a set of strings – Instead of sorting or horizontal scanning, insert every string into a Trie and walk down while the current node has exactly one child and is not an end‑of‑word. The path you traverse is the answer.

Both questions appear frequently in frontend and backend interviews because they test whether you can think beyond linear scans and appreciate hierarchical data.

Why This New Power Matters

With a Trie in your toolkit, autocomplete goes from a “nice‑to‑have” feature that chugs on large data sets to a snappy, instantaneous experience that scales to millions of entries. You’ll notice the difference in:

• Response time – keystrokes feel instant, even with a 500 k‑word dictionary.
• Memory efficiency – shared prefixes mean you store common parts only once (often far less than N × average length).
• Extensibility – adding weighting, fuzzy matching, or persistence becomes a matter of augmenting the node structure, not rewriting the core logic.

Seeing the autocomplete widget spring to life after I swapped the naive filter for a Trie was a genuine “I feel like a superhero” moment. It reminded me that the right abstraction can turn a frustrating bottleneck into a delightful feature.

---

Your turn: Grab a list of your favorite movie titles, insert them into a Trie, and build a tiny “type‑to‑search” demo in the browser. Try adding a counter to each node to rank suggestions by popularity. Share your CodePen or GitHub gist – I’d love to see what you build! 🚀