Autocomplete System with Trie in DSA C++ - 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 next char node

↓

Mark end of word

↓

End Insert

↓

Start Autocomplete Query

↓

Traverse Trie for prefix chars

↓

If prefix node missing: Return empty

↓

From prefix node: DFS to find all words

↓

Return list of words

Insert words character by character into the Trie, creating nodes as needed. For autocomplete, traverse the Trie by prefix, then collect all words below that prefix.

Execution Sample

DSA C++

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

Insert words 'cat', 'car', 'dog' 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	Create node 'c' from root	root -> c -> null
2	Insert 'cat' char 'a'	Root -> c -> a	Create node 'a' from 'c'	root -> c -> a -> null
3	Insert 'cat' char 't'	Root -> c -> a -> t	Create node 't' from 'a'	root -> c -> a -> t*
4	Insert 'car' char 'c'	Root -> c -> a -> t*	Node 'c' exists, move to 'c'	root -> c -> a -> t*
5	Insert 'car' char 'a'	Root -> c -> a -> t*	Node 'a' exists, move to 'a'	root -> c -> a -> t*
6	Insert 'car' char 'r'	Root -> c -> a -> t*, r	Create node 'r' from 'a'	root -> c -> a -> t*, r*
7	Insert 'dog' char 'd'	Root -> c -> a -> t*, r*; d	Create node 'd' from root	root -> c -> a -> t*, r*; d -> null
8	Insert 'dog' char 'o'	Root -> c -> a -> t*, r*; d -> o	Create node 'o' from 'd'	root -> c -> a -> t*, r*; d -> o -> null
9	Insert 'dog' char 'g'	Root -> c -> a -> t*, r*; d -> o -> g	Create node 'g' from 'o'	root -> c -> a -> t*, r*; d -> o -> g*
10	Autocomplete 'ca' prefix traversal	Root -> c -> a -> t*, r*; d -> o -> g*	Traverse root->c->a	At node 'a' with children 't*', 'r*'
11	DFS from 'a' to find words	Root -> c -> a -> t*, r*; d -> o -> g*	Visit 't*' and 'r*' nodes	Found words: 'cat', 'car'
12	Return autocomplete results	Root -> c -> a -> t*, r*; d -> o -> g*	Return ['cat', 'car']	Autocomplete output: ['cat', 'car']

💡 Autocomplete ends after collecting all words under prefix node 'a'.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12
Trie Nodes	root only	root -> c -> a -> t*	root -> c -> a -> t*, r*	root -> c -> a -> t*, r*; d -> o -> g*	No change (search complete)
Current Node	root	at 't' after inserting 'cat'	at 'r' after inserting 'car'	at 'g' after inserting 'dog'	at 'a' after prefix traversal
Autocomplete Results	empty	empty	empty	empty	['cat', 'car']

Key Moments - 3 Insights

Why do we create new nodes only if the character node doesn't exist?

Because existing nodes represent shared prefixes. See steps 4 and 5 where 'c' and 'a' nodes already exist, so we reuse them instead of creating duplicates.

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

We mark the last character node of a word with a special flag (shown as '*'). For example, 't*' and 'r*' in steps 3 and 6 indicate word ends.

What happens if the prefix is not found during autocomplete?

The traversal stops early and returns empty. In the execution table, step 10 shows traversal reaching node 'a'. If 'a' was missing, autocomplete would return empty immediately.

Visual Quiz - 3 Questions

Look at the execution table at step 6. Which new node is created?

A Node 'd' from root

B Node 'r' from 'a'

C Node 't' from 'a'

D Node 'o' from 'd'

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6.

At which step does the Trie first contain the complete word 'dog'?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look for the step where node 'g*' is created, marking the end of 'dog'.

If we autocomplete prefix 'do', what would be the output?

A ['dog']

B ['cat', 'car']

C []

D ['do']

💡 Hint

Refer to the Trie structure after step 9 and the DFS process in step 11.

Concept Snapshot

Trie stores words by characters in nodes.
Insert: create nodes for missing chars, mark word end.
Autocomplete: traverse prefix, then DFS to collect words.
Shared prefixes reuse nodes, saving space.
Word end marked by special flag on node.
Efficient prefix search for autocomplete.

Full Transcript

We build a Trie by inserting words character by character. Each character is a node linked from the previous. If a character node exists, we reuse it to share prefixes. The end of a word is marked specially. For autocomplete, we traverse the Trie nodes matching the prefix characters. If the prefix exists, we do a depth-first search from that node to find all complete words below it. This way, autocomplete returns all words starting with the prefix efficiently.