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.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To efficiently store and search prefixes of words

B. To sort words alphabetically

C. To count the frequency of words

D. To encrypt the stored words

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure designed to store strings by their prefixes, allowing fast prefix-based searches.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires quick lookup of words starting with a given prefix, which Trie supports efficiently.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option A

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is built for prefix-based fast search [OK]

Common Mistakes:

• Confusing Trie with sorting algorithms
• Thinking Trie encrypts data
• Assuming Trie counts word frequency only

2. Which of the following is the correct TypeScript syntax to define a Trie node with children as a Map of characters to Trie nodes?

easy

A. class TrieNode { children: Array<string> = []; isEnd: boolean = false; }

B. class TrieNode { children: Map = new Map(); isEnd: boolean = false; }

C. class TrieNode { children: string[] = []; isEnd: boolean = true; }

D. class TrieNode { children: Map = new Map(); isEnd: boolean = false; }

Solution

1. Step 1: Identify correct data type for children

   Children should map characters (string) to TrieNode objects, so Map is correct.

2. Step 2: Check initialization and isEnd flag

   Children initialized as new Map(), and isEnd defaults to false indicating not end of word initially.

3. Final Answer:

   class TrieNode { children: Map = new Map(); isEnd: boolean = false; } -> Option B

4. Quick Check:

   Map for children [OK]

Hint: Children map chars to nodes using Map [OK]

Common Mistakes:

• Using array instead of Map for children
• Using number keys instead of string keys
• Setting isEnd to true by default

3. Given the following TypeScript code snippet for inserting words into a Trie and searching for prefix suggestions, what will be the output of autocomplete.getSuggestions('ca')?

class TrieNode {
  children: Map = new Map();
  isEnd: boolean = false;
}

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

  insert(word: string) {
    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)!;
    }
    node.isEnd = true;
  }

  getSuggestions(prefix: string): string[] {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children.has(char)) return [];
      node = node.children.get(char)!;
    }
    const results: string[] = [];
    const dfs = (currNode: TrieNode, path: string) => {
      if (currNode.isEnd) results.push(path);
      for (const [ch, nextNode] of currNode.children) {
        dfs(nextNode, path + ch);
      }
    };
    dfs(node, prefix);
    return results;
  }
}

const autocomplete = new AutocompleteSystem();
autocomplete.insert('cat');
autocomplete.insert('car');
autocomplete.insert('cap');
autocomplete.insert('dog');
console.log(autocomplete.getSuggestions('ca'));

medium

A. ["cat", "car"]

B. ["dog"]

C. []

D. ["cat", "car", "cap"]

Solution

1. Step 1: Insert words and traverse prefix 'ca'

   Words 'cat', 'car', 'cap' are inserted. Searching prefix 'ca' finds node with children 't', 'r', 'p'.

2. Step 2: DFS collects all words starting with 'ca'

   DFS from 'ca' node collects 'cat', 'car', and 'cap' as all end nodes under that prefix.

3. Final Answer:

   ["cat", "car", "cap"] -> Option D

4. Quick Check:

   Prefix 'ca' matches cat, car, cap [OK]

Hint: DFS from prefix node collects all words [OK]

Common Mistakes:

• Returning empty list if prefix found
• Returning unrelated words like 'dog'
• Missing one or more words starting with prefix

4. The following TypeScript code for the insert method in a Trie has a bug. What is the bug?

insert(word: string) {
  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);
  }
  node.isEnd = true;
}

medium

A. Missing non-null assertion operator (!) when getting child node

B. Children map should be an array, not Map

C. isEnd should be set to false, not true

D. Loop should iterate over indices, not characters

Solution

1. Step 1: Identify potential null or undefined access

   node.children.get(char) can return undefined if key missing, so TypeScript requires non-null assertion or check.

2. Step 2: Fix by adding non-null assertion operator

   Adding '!' after get(char) tells TypeScript the value is not undefined, fixing the bug.

3. Final Answer:

   Missing non-null assertion operator (!) when getting child node -> Option A

4. Quick Check:

   Use get(char)! to avoid undefined [OK]

Hint: Use '!' after get() to assure non-null [OK]

Common Mistakes:

• Ignoring TypeScript undefined error
• Changing data structure unnecessarily
• Setting isEnd incorrectly

5. You want to extend the autocomplete system to return suggestions sorted by their frequency of insertion (most frequent first). Which data structure modification is best to support this efficiently?

hard

A. Store all words in a separate array and sort on each query

B. Use a binary search tree instead of a Trie

C. Add a frequency count field to each Trie node marking end of word

D. Remove the isEnd flag and rely on children count

Solution

1. Step 1: Understand frequency tracking in Trie

   Adding a frequency count to nodes marking word ends allows tracking how often each word was inserted.

2. Step 2: Use frequency to sort suggestions efficiently

   During DFS for suggestions, use frequency counts to sort or prioritize words without extra data structures.

3. Final Answer:

   Add a frequency count field to each Trie node marking end of word -> Option C

4. Quick Check:

   Frequency field in Trie nodes enables sorting [OK]

Hint: Track frequency in nodes to sort suggestions fast [OK]

Common Mistakes:

• Sorting all words on each query (slow)
• Replacing Trie with BST loses prefix efficiency
• Removing isEnd loses word boundary info