Building Autocomplete Like a Jedi: Trie from Scratch

The Quest Begins (The "Why")

I still remember the first time I was asked in an interview to “build an autocomplete feature from scratch.” My brain went straight to the usual solution: dump all possible completions into an array, filter it on every keystroke, and hope the dataset stays tiny. Spoiler: it didn’t stay tiny, and the interviewer’s eyes glazed over as I watched my O(n²) nightmare crawl.

That moment felt like staring down a dragon made of brute‑force loops while I only had a wooden spoon. I knew there had to be a smarter way—something that could give me instant suggestions even when the dictionary held hundreds of thousands of words. The dragon wasn’t going to be slayed by sheer force; I needed a clever sword.

The Revelation (The Insight)

The sword turned out to be a Trie (pronounced “try”), also called a prefix tree. At its core, a Trie is just a tree where each node represents a single character, and a path from the root to a node spells out a prefix. If you mark a node as “the end of a word,” you’ve stored that word.

Why does this give us lightning‑fast autocomplete?

• Prefix‑centric layout – All words that share a prefix live in the same subtree. To find suggestions for “jap”, you only need to wander down the j → a → p branch and collect everything underneath. No scanning unrelated words.
• Linear work per character – Inserting or looking up a word touches exactly one node per letter. If the word length is L, the cost is O(L).
• Output‑sensitive retrieval – Gathering the completions costs O(P + K), where P is the length of the prefix and K is the number of characters in the returned words. In other words, you pay only for what you actually need to return.

Think of it like walking down a hallway of doors (each door is a letter). Instead of checking every room in the building for people whose names start with “Ja”, you go straight to the “Ja” hallway and knock on every door there.

I was shocked when I first saw how tiny the memory footprint could be compared to storing every possible suffix. It felt like unlocking the secret level in Portal—the solution was there all along, just hidden behind a different perspective.

Wielding the Power (Code & Examples)

The Naïve Attempt (The Struggle)

// Autocomplete with a simple array + filter (O(n) per query)
const dictionary = ['apple', 'app', 'application', 'banana', 'band', 'bandana'];

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

Fine for a handful of words, but imagine dictionary holds 500 k entries. Each keystroke scans half a million strings—yeah, not ideal.

The Trie Solution (The Victory)

Below is a compact, production‑ready Trie in JavaScript. I’ve added comments to highlight the “why” behind each block.

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

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

  // Insert a word – O(L) where L = 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.isWord = true; // mark the end
  }

  // Find the node that represents the prefix – O(P)
  _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;
  }

  // Check if a word exists – O(L)
  search(word) {
    const node = this._findNode(word);
    return node !== null && node.isWord;
  }

  // Collect all words under a given node – DFS
  _collectWords(node, prefix, results) {
    if (node.isWord) results.push(prefix);
    for (const [ch, child] of node.children.entries()) {
      this._collectWords(child, prefix + ch, results);
    }
  }

  // Autocomplete: return all words that start with prefix – O(P + K)
  autocomplete(prefix) {
    const node = this._findNode(prefix);
    if (!node) return []; // no matches
    const suggestions = [];
    this._collectWords(node, prefix, results);
    return suggestions;
  }
}

How to use it

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

console.log(trie.autocomplete('ban')); // ['band', 'bandana', 'banana']
console.log(trie.search('app'));       // true
console.log(trie.search('appl'));      // false (not a full word)

Common Traps (The “Don’t Step Here” Signs)

1. Forgetting the isWord flag – If you only rely on the presence of children, you’ll mistakenly treat prefixes as complete words (e.g., “app” would appear as a word even if you never inserted it).
2. Mutating the same array during DFS – Reusing a single string builder without copying can lead to corrupted results because the same reference gets altered across recursive calls.
3. Assuming the Trie is always balanced – Depth depends on word length, not number of words, so a very long word (think a German compound) can make a single query slower, but it’s still O(L) where L is that word’s length—not O(N) over the whole set.

Real‑World Interview Flavors

• LeetCode 208 – Implement Trie (Prefix Tree) – Classic insert/search/startsWith.
• LeetCode 648 – Replace Words – Given a dictionary of roots, replace each word in a sentence with its shortest root. The Trie lets you find the shortest prefix in O(L) per word, turning an O(N·M) brute force into O(total characters).
• Google’s “Design an Autocomplete System” – You’re asked to handle hot sentences with frequencies. The Trie stores the sentences; a auxiliary hash map keeps counts, and you retrieve top‑k suggestions via a DFS that picks the highest frequencies.

All of these boil down to the same insight: prefix‑based look‑ups are cheap when you organize data by prefix.

Why This New Power Matters

Now that you’ve got the Trie spell in your grimoire, you can:

• Build instant‑search boxes that stay snappy even with massive catalogs (think e‑commerce product names or code‑base symbol lookup).
• Implement spell‑checkers that suggest corrections by walking the Trie and allowing a limited number of edits.
• Autocomplete IDEs, CLI tools, or even chatbots—anywhere users type and expect quick, relevant continuations.

The best part? The core idea is tiny enough to explain in a whiteboard interview, yet powerful enough to power production systems at scale. When I finally got the Trie working in that interview, I felt like I’d just defeated the dragon with a single, precise strike—no wooden spoon required.

Your Turn

Grab a list of your favorite movie titles, song lyrics, or even the vocabulary from your last project. Build a Trie, feed it the data, and try to autocomplete user input in real time. Then, level up: add a frequency count and return the top‑3 most popular completions.

Share your solution in the comments, or tweet a snippet with #TrieQuest. I can’t wait to see what you’ll build!

---

Happy coding, and may your prefixes always be short and your suggestions spot‑on!