Autocomplete System with Trie in DSA Typescript - Execution Trace

Concept Flow - Autocomplete System with Trie

Start: Insert words into Trie

↓

For each word: For each char

↓

If char node missing: Create node

↓

Move to char node

↓

Mark end of word

↓

Autocomplete query: Traverse Trie by prefix

↓

If prefix node found: DFS to collect words

↓

Return list of words starting with prefix

Build a Trie by inserting words character by character, then find autocomplete suggestions by traversing the Trie nodes matching the prefix and collecting all words below.

Execution Sample

DSA Typescript

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

// Insert 'cat'
// Insert 'car'
// Autocomplete 'ca'

Insert words 'cat' and 'car' into the Trie, then find all words starting with prefix 'ca'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'c'	Root -> c	Create node for 'c' under root	root └─ c
2	Insert 'a' after 'c'	Root -> c -> a	Create node for 'a' under 'c'	root └─ c └─ a
3	Insert 't' after 'a'	Root -> c -> a -> t (word end)	Create node for 't' under 'a', mark isWordEnd	root └─ c └─ a └─ t*
4	Insert 'c' (existing)	Root -> c -> a -> t*	Reuse node 'c' at root	root └─ c └─ a └─ t*
5	Insert 'a' (existing)	Root -> c -> a -> t*	Reuse node 'a' under 'c'	root └─ c └─ a └─ t*
6	Insert 'r' after 'a'	Root -> c -> a -> t*, r (word end)	Create node 'r' under 'a', mark isWordEnd	root └─ c └─ a ├─ t* └─ r*
7	Autocomplete 'ca' prefix	Traverse root -> c -> a	Pointer moves to node 'a'	At node 'a' with children 't*' and 'r*'
8	Collect words from 'a' node	Words found: 'cat', 'car'	DFS visits 't*' and 'r*' nodes	Suggestions: ['cat', 'car']
9	Return suggestions	Autocomplete complete	Return ['cat', 'car']	Output: ['cat', 'car']

💡 All characters inserted and prefix traversal complete, suggestions collected.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	After Step 7	Final
Trie Root	Empty	Has child 'c'	Has path c->a->t*	Has path c->a->t*, r*	Pointer at node 'a'	Pointer at node 'a'
Current Node	Root	Node 'c'	Node 't'	Node 'r'	Node 'a'	Node 'a'
isWordEnd flags	None	None	't' true	't' and 'r' true	't' and 'r' true	't' and 'r' true
Suggestions List	Empty	Empty	Empty	Empty	Empty	['cat', 'car']

Key Moments - 3 Insights

Why do we create new nodes only if the character node does not exist?

Because existing nodes represent shared prefixes, so we reuse them to save space and avoid duplicates. See execution_table steps 4 and 5 where 'c' and 'a' nodes are reused.

How do we know when a word ends in the Trie?

We mark the last character node of a word with isWordEnd = true. In execution_table step 3 and 6, nodes 't' and 'r' are marked to indicate 'cat' and 'car' are complete words.

How does autocomplete find all words starting with a prefix?

After reaching the prefix node, we perform a depth-first search (DFS) to collect all words below it. See execution_table step 8 where DFS visits 't*' and 'r*' nodes to find 'cat' and 'car'.

Visual Quiz - 3 Questions

Look at the execution_table, what is the visual state after step 6?

A root └─ c └─ a └─ t*

B root └─ c └─ a ├─ t* └─ r*

C root └─ c └─ r*

D root └─ a └─ t*

💡 Hint

Check the Visual State column in execution_table row for step 6.

At which step does the pointer move to the prefix node 'a' during autocomplete?

A Step 7

B Step 5

C Step 3

D Step 9

💡 Hint

Look at the Pointer Changes column in execution_table for step 7.

If we insert the word 'cap' after 'car', how would the Trie nodes under 'a' change?

A Add a new child node 'p' under 'c'

B Replace node 'r' with 'p'

C Add a new child node 'p' under 'a' marked as word end

D No change, 'cap' is ignored

💡 Hint

New words add new nodes for characters not already present under the prefix node.

Concept Snapshot

Autocomplete with Trie:
- Insert words char by char, creating nodes if missing
- Mark last char node as word end
- For prefix search, traverse Trie nodes matching prefix
- From prefix node, DFS to collect all words
- Efficient prefix-based word retrieval
- Shared prefixes save space and speed up search

Full Transcript

This visualization shows how an autocomplete system uses a Trie data structure. Words are inserted one character at a time, creating new nodes only when needed. Each word's last character node is marked to indicate a complete word. To autocomplete, we traverse the Trie to the prefix node, then collect all words below it using depth-first search. The execution table tracks each insertion and traversal step, showing how nodes are created and reused. The variable tracker follows pointers and word-end flags. Key moments clarify why nodes are reused, how word ends are marked, and how autocomplete collects suggestions. The quiz tests understanding of Trie structure and traversal steps.

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