Autocomplete System with Trie in DSA Javascript

Mental Model

A trie stores words by sharing common prefixes, so we can quickly find all words starting with a given prefix.

Analogy: Imagine a tree of roads where each road sign is a letter. To find all places starting with 'ca', you follow the roads for 'c' then 'a' and see all destinations branching from there.

root
 ↓
 c -> a -> t (word end)
       ↓
       r -> null

Each arrow is a letter link; nodes mark letters; some nodes mark word ends.

Dry Run Walkthrough

Input: Insert words: 'cat', 'car', 'cart', then autocomplete prefix 'ca'

Goal: Build trie with words and find all words starting with 'ca'

Step 1: Insert 'cat' letter by letter

root -> c -> a -> t* -> null

Why: Create path for 'cat' marking 't' as word end

Step 2: Insert 'car' sharing prefix 'ca'

root -> c -> a -> t* -> null
                 ↓
                 r* -> null

Why: Reuse 'c' and 'a', add new branch 'r' marked as word end

Step 3: Insert 'cart' extending from 'car'

root -> c -> a -> t* -> null
                 ↓
                 r* -> t* -> null

Why: Add 't' after 'r' marking new word end for 'cart'

Step 4: Autocomplete prefix 'ca' by traversing trie

At node 'a' under 'c', collect words: 'cat', 'car', 'cart'

Why: All words starting with 'ca' are under this node

Result:

root -> c -> a -> t* -> null
                 ↓
                 r* -> t* -> null
Autocomplete results: ['cat', 'car', 'cart']

Annotated Code

DSA Javascript

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

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char); // advance node to child
    }
    node.isWord = true; // mark end of word
  }

  _dfs(node, prefix, results) {
    if (node.isWord) {
      results.push(prefix); // found a word
    }
    for (const [char, child] of node.children) {
      this._dfs(child, prefix + char, results); // explore deeper
    }
  }

  autocomplete(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return []; // prefix not found
      }
      node = node.children.get(char); // move to prefix node
    }
    const results = [];
    this._dfs(node, prefix, results); // collect all words
    return results;
  }
}

// Driver code
const trie = new Trie();
['cat', 'car', 'cart'].forEach(word => trie.insert(word));
const completions = trie.autocomplete('ca');
console.log(completions.join(', '));

node = node.children.get(char); // advance node to child

advance node to next letter node to build path

node.isWord = true; // mark end of word

mark current node as a complete word

if (!node.children.has(char)) { return []; }

stop if prefix path missing, no completions

this._dfs(node, prefix, results); // collect all words

collect all words starting from prefix node

if (node.isWord) { results.push(prefix); }

add word to results when word end found

Output

cat, car, cart

Complexity Analysis

Time: O(m + n) where m is prefix length and n is total letters in matched words because we traverse prefix then collect all completions

Space: O(n) for storing all inserted words in trie nodes

vs Alternative: Compared to scanning all words linearly (O(k * w) where k is prefix length and w is number of words), trie is faster for autocomplete by avoiding full scans

Edge Cases

Empty prefix

Returns all words stored in trie

DSA Javascript

if (!node.children.has(char)) { return []; }

Prefix not in trie

Returns empty list immediately

DSA Javascript

if (!node.children.has(char)) { return []; }

Words with shared prefixes

Trie branches correctly share nodes without duplication

DSA Javascript

if (!node.children.has(char)) { node.children.set(char, new TrieNode()); }

When to Use This Pattern

When you need to quickly find all words starting with a prefix, use a trie because it organizes words by shared prefixes for fast lookup.

Common Mistakes

Mistake: Not marking the end of a word, so autocomplete returns incomplete results
Fix: Set isWord = true at the last node of each inserted word

Mistake: Not checking if prefix exists before DFS, causing errors or wrong results
Fix: Return empty list if prefix path is missing before collecting completions

Summary

Stores words in a tree structure to quickly find all words starting with a given prefix.

Use when you want fast autocomplete suggestions from a large word list.

The key is sharing prefix nodes so you only explore relevant branches for the prefix.