Autocomplete System with Trie in DSA C# - Execution Trace

Concept Flow - Autocomplete System with Trie

Start: Input prefix

↓

Traverse Trie from root

↓

For each character in prefix

↓

Check if child node exists

↓

Move to child

↓

Collect all words from current node

↓

Return list of completions

The system takes a prefix, moves down the trie nodes matching each character, then collects all words starting from that node as autocomplete suggestions.

Execution Sample

DSA C#

Insert("cat")
Insert("car")
Insert("cart")
Autocomplete("ca")

Insert words 'cat', 'car', 'cart' into trie, then find all words starting with 'ca'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' char 'c'	root -> c	root.children['c'] created	root -> c -> null
2	Insert 'cat' char 'a'	root -> c -> a	c.children['a'] created	root -> c -> a -> null
3	Insert 'cat' char 't'	root -> c -> a -> t	a.children['t'] created, mark 't' as end of word	root -> c -> a -> t*
4	Insert 'car' char 'c'	root -> c -> a -> t*	No new node, move to 'c'	root -> c -> a -> t*
5	Insert 'car' char 'a'	root -> c -> a -> t*	No new node, move to 'a'	root -> c -> a -> t*
6	Insert 'car' char 'r'	root -> c -> a -> t*	a.children['r'] created, mark 'r' as end of word	root -> c -> a -> t*, r*
7	Insert 'cart' char 'c'	root -> c -> a -> t*, r*	No new node, move to 'c'	root -> c -> a -> t*, r*
8	Insert 'cart' char 'a'	root -> c -> a -> t*, r*	No new node, move to 'a'	root -> c -> a -> t*, r*
9	Insert 'cart' char 'r'	root -> c -> a -> t*, r*	No new node, move to 'r'	root -> c -> a -> t*, r*
10	Insert 'cart' char 't'	root -> c -> a -> t*, r*	r.children['t'] created, mark 't' as end of word	root -> c -> a -> t*, r* -> t*
11	Autocomplete 'ca' char 'c'	root -> c -> a -> t*, r* -> t*	Move to child 'c'	At node 'c'
12	Autocomplete 'ca' char 'a'	root -> c -> a -> t*, r* -> t*	Move to child 'a'	At node 'a'
13	Collect words from node 'a'	root -> c -> a -> t*, r* -> t*	Traverse children 't', 'r'	Found words: 'cat', 'car', 'cart'

💡 All prefix characters processed; collected all words starting with 'ca'

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 10	After Step 13
Trie Nodes	root only	root->c->a->t*	root->c->a->t*, r*	root->c->a->t*, r*->t*	No change
Current Node	root	root	root	root	node 'a'
Collected Words	[]	[]	[]	[]	["cat", "car", "cart"]

Key Moments - 3 Insights

Why do we create new nodes only when the child does not exist?

Because existing nodes represent prefixes already stored. See steps 4-6 where 'c' and 'a' nodes exist, so no new nodes are created.

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

We mark the last character node of a word as an end node. For example, in step 3 't' is marked as end of 'cat'.

How does autocomplete collect all words from a prefix node?

It traverses all child nodes recursively from the prefix node, collecting words at nodes marked as end. See step 13 collecting 'cat', 'car', 'cart'.

Visual Quiz - 3 Questions

Look at the execution table, what nodes exist after step 6?

A root -> c -> a -> t* only

B root -> c -> a -> t* and r*

C root -> c -> a only

D root only

💡 Hint

Check the 'Nodes in Trie' column at step 6 in the execution_table

At which step is the node for 'r' created during insertion?

A Step 3

B Step 10

C Step 6

D Step 13

💡 Hint

Look at the 'Pointer Changes' column for when 'r' child is created

If we autocomplete prefix 'car', which step in the table shows moving to node 'r'?

A No such step

B Step 12

C Step 11

D Step 13

💡 Hint

Autocomplete steps only show moving to 'c' and 'a' nodes; 'r' is not explicitly shown

Concept Snapshot

Autocomplete with Trie:
- Insert words by creating nodes for each char
- Mark end of word nodes
- For autocomplete, traverse prefix nodes
- Collect all words from prefix node recursively
- Efficient prefix search with shared nodes

Full Transcript

This visualization shows how an autocomplete system uses a trie data structure. Words like 'cat', 'car', and 'cart' are inserted by creating nodes for each character. Nodes are only created if they don't exist, sharing prefixes. Each word's last character node is marked to indicate word end. To autocomplete, the system traverses the trie nodes matching the prefix characters. Once at the prefix node, it collects all words by exploring child nodes recursively. The execution table tracks each insertion and traversal step, showing how the trie grows and how autocomplete finds matching words.

Practice

1. What is the main advantage of using a Trie over a HashSet for implementing an autocomplete system?

easy

A. Trie uses less memory than HashSet for all cases

B. Trie supports prefix-based search efficiently, while HashSet requires checking all words

C. Trie is faster for exact word lookup than HashSet

D. Trie automatically sorts words alphabetically unlike HashSet

Solution

1. Step 1: Understand autocomplete requirement

   Autocomplete needs to find all words that start with a given prefix quickly.

2. Step 2: Compare Trie vs HashSet

   Trie stores characters level by level, so prefix traversal is O(prefix length). HashSet requires scanning all words to check which ones start with the prefix.

3. Final Answer:

   Trie supports prefix-based search efficiently, while HashSet requires checking all words -> Option B

4. Quick Check:

   Trie = prefix search in O(m), HashSet = O(n*m) for prefix [OK]

Hint: Trie shares common prefixes among words - natural fit for autocomplete [OK]

Common Mistakes:

• Assuming Trie always uses less memory - it can use more for sparse word sets
• Thinking exact lookup is why Trie beats HashSet - HashSet is actually faster for exact lookup
• Assuming Trie sorts automatically - it doesn't sort, traversal order depends on children insertion

2. Which C# code correctly inserts a word into a Trie node structure where each node has a Dictionary<char, TrieNode> Children and a bool IsEndOfWord?

easy

A. node.Children[c] = new TrieNode(); node = node.Children[c];

B. if (!node.Children.ContainsKey(c)) node.Children[c] = new TrieNode(); node = node.Children[c];

C. node.Children.Add(c); node = node.Children[c];

D. node.Children[c] = c; node = node.Children[c];

Solution

1. Step 1: Check if child exists

   Before creating a new node, check if the character key already exists in Children to avoid overwriting existing subtrees.

2. Step 2: Create only if missing

   Using ContainsKey check ensures we reuse existing nodes and only create new ones when the character path doesn't exist yet.

3. Final Answer:

   if (!node.Children.ContainsKey(c)) node.Children[c] = new TrieNode(); node = node.Children[c]; -> Option B

4. Quick Check:

   Always check ContainsKey before adding to avoid overwriting existing paths [OK]

Hint: Always guard with ContainsKey before inserting a new Trie node [OK]

Common Mistakes:

• Option A overwrites existing children, destroying previously inserted words
• Option C uses Add which throws if key already exists
• Option D stores char as value instead of TrieNode

3. What will the following C# Trie prefix search return when searching for prefix "ca" in a Trie containing ["cat", "car", "card", "dog"]?

List<string> results = new List<string>();
void DFS(TrieNode node, string current) {
    if (node.IsEndOfWord) results.Add(current);
    foreach (var kvp in node.Children)
        DFS(kvp.Value, current + kvp.Key);
}
TrieNode prefixNode = GetPrefixNode("ca");
if (prefixNode != null) DFS(prefixNode, "ca");

medium

A. ["cat", "car", "card", "dog"]

B. ["ca"]

C. ["cat", "car", "card"]

D. []

Solution

1. Step 1: Find prefix node

   GetPrefixNode("ca") traverses c→a and returns the node at 'a'. "dog" is unreachable from this node.

2. Step 2: DFS from prefix node

   DFS explores all children from 'a': t (cat), r (car), r→d (card). All three have IsEndOfWord=true.

3. Final Answer:

   ["cat", "car", "card"] -> Option C

4. Quick Check:

   Only words under prefix "ca" subtree are returned, "dog" excluded [OK]

Hint: DFS from prefix node returns only words in that subtree - "dog" is in a different branch [OK]

Common Mistakes:

• Including 'dog' - it's in a completely separate Trie branch
• Returning only 'ca' - 'ca' itself is not marked IsEndOfWord
• Returning empty - prefix 'ca' exists in the Trie so DFS finds words

4. Identify the bug in this C# autocomplete prefix search:

bool StartsWith(string prefix) {
    TrieNode node = root;
    foreach (char c in prefix) {
        if (!node.Children.ContainsKey(c))
            return true;
        node = node.Children[c];
    }
    return false;
}

medium

A. Should return false when character not found, and true at the end

B. Should use a List instead of Dictionary for Children

C. Should check IsEndOfWord instead of ContainsKey

D. Should start from the last character of the prefix

Solution

1. Step 1: Trace the logic

   When a character is not found in Children, it means the prefix doesn't exist - should return false, not true. And after traversing all prefix characters successfully, the prefix exists - should return true.

2. Step 2: Identify the swap

   The return values are swapped: 'return true' and 'return false' are in each other's place.

3. Final Answer:

   Should return false when character not found, and true at the end -> Option A

4. Quick Check:

   Missing prefix char = false, full prefix traversed = true [OK]

Hint: If you can't follow the path, prefix is absent = false; if path complete = true [OK]

Common Mistakes:

• Thinking Dictionary is wrong - Dictionary is correct for Children
• Checking IsEndOfWord - StartsWith only checks if prefix path exists, not word end
• Starting from last character - prefix traversal always goes left to right

5. In a Trie-based autocomplete system with 100,000 words averaging 8 characters each, what is the time complexity to retrieve all words matching a prefix of length p, where k is the number of matching words and m is the average word length?

hard

A. O(n) where n is total number of words

B. O(p + k * m) - traverse prefix then DFS over matching words

C. O(p * n) - check prefix against each word

D. O(1) - Trie provides constant time autocomplete

Solution

1. Step 1: Cost of reaching prefix node

   Traversing p characters to reach the prefix node costs O(p).

2. Step 2: Cost of DFS to collect results

   DFS visits all nodes under the prefix subtree. With k matching words of average length m, this costs O(k * m) in the worst case.

3. Final Answer:

   O(p + k * m) -> Option B

4. Quick Check:

   Prefix traversal O(p) + result collection O(k*m) = O(p + k*m) [OK]

Hint: Trie autocomplete = prefix path O(p) + collect results O(k*m), independent of total word count n [OK]

Common Mistakes:

• O(n) - Trie doesn't scan all words, only the prefix subtree
• O(1) - result collection depends on number and length of matching words
• O(p*n) - that's the HashSet approach, not Trie