Autocomplete System with Trie in DSA Typescript

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 shops starting with 'ca', you follow the roads for 'c' then 'a' and see all shops on that branch.

root
 ↓
 c -> a -> t [end]
       ↓
       r -> e [end]

Dry Run Walkthrough

Input: words: ["cat", "car", "care"], prefix: "ca"

Goal: Find all words starting with prefix "ca"

Step 1: Start at root, follow 'c' node

root -> [c]

Why: We need to find the branch for the first letter of prefix

Step 2: From 'c', follow 'a' node

root -> c -> [a]

Why: Continue following prefix letters to reach prefix end

Step 3: Collect all words from 'a' node subtree: 'cat', 'car', 'care'

root -> c -> a -> t [end]
               ↓
               r -> e [end]

Why: All words under 'a' start with prefix 'ca'

Result:

Words with prefix 'ca': ["cat", "car", "care"]

Annotated Code

DSA Typescript

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEndOfWord: boolean = false;
}

class Trie {
  root: TrieNode = new TrieNode();

  insert(word: string): void {
    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.isEndOfWord = true; // mark end of word
  }

  searchPrefix(prefix: string): TrieNode | null {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return null; // prefix not found
      }
      node = node.children.get(char)!; // advance node
    }
    return node; // node at prefix end
  }

  collectAllWords(node: TrieNode, prefix: string, results: string[]): void {
    if (node.isEndOfWord) {
      results.push(prefix); // found a word
    }
    for (const [char, childNode] of node.children) {
      this.collectAllWords(childNode, prefix + char, results); // recurse children
    }
  }

  autocomplete(prefix: string): string[] {
    const results: string[] = [];
    const node = this.searchPrefix(prefix);
    if (!node) return results; // no words with prefix
    this.collectAllWords(node, prefix, results); // gather words
    return results;
  }
}

// Driver code
const trie = new Trie();
["cat", "car", "care"].forEach(word => trie.insert(word));
const prefix = "ca";
const completions = trie.autocomplete(prefix);
console.log(`Words with prefix '${prefix}': ["${completions.join('", "')}"]`);

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

Create new child node if letter path missing

node = node.children.get(char)!;

Advance node pointer to child node for current letter

node.isEndOfWord = true;

Mark node as end of a valid word

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

Stop search if prefix letter path missing

return node;

Return node at end of prefix path

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

Add word to results when end of word reached

this.collectAllWords(childNode, prefix + char, results);

Recursively explore all child nodes to collect words

const node = this.searchPrefix(prefix); if (!node) return results;

Find prefix node or return empty if not found

this.collectAllWords(node, prefix, results);

Collect all words starting from prefix node

Output

Words with prefix 'ca': ["cat", "car", "care"]

Complexity Analysis

Time: O(m + k) where m is prefix length and k is total characters in matched subtree because we traverse prefix then collect all words

Space: O(n) for storing all words in trie nodes, where n is total characters in all words

vs Alternative: Compared to scanning all words for prefix (O(n * m)), trie reduces prefix search to O(m) plus output size, making autocomplete efficient

Edge Cases

Empty prefix

Returns all words stored in trie

DSA Typescript

const node = this.searchPrefix(prefix); if (!node) return results;

Prefix not in trie

Returns empty list immediately

DSA Typescript

if (!node) return results;

Words with shared prefixes

All words under prefix node are collected correctly

DSA Typescript

this.collectAllWords(node, prefix, results);

When to Use This Pattern

When asked to find all words starting with a prefix efficiently, use a trie to quickly navigate prefix letters and gather completions.

Common Mistakes

Mistake: Not marking end of word nodes, causing incomplete or incorrect autocomplete results
Fix: Set isEndOfWord = true at the last node of each inserted word

Mistake: Not returning empty list when prefix not found, causing errors
Fix: Check if prefix node exists; if null, return empty list immediately

Summary

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

Use when you need fast autocomplete suggestions from a large dictionary of words.

The key insight is that common prefixes share the same path, so searching prefix is fast and gathering words is localized.