Autocomplete System with Trie in DSA Go - Execution Trace

Concept Flow - Autocomplete System with Trie

Start: Insert words into Trie

↓

Build Trie nodes for each char

↓

Mark end of word nodes

↓

User inputs prefix

↓

Traverse Trie for prefix

↓

If prefix found: DFS from prefix node

↓

Collect all words with prefix

↓

Return autocomplete suggestions

Build a Trie by inserting words character by character, then traverse the Trie using the input prefix to find all words starting with that prefix.

Execution Sample

DSA Go

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

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

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' char 'c'	Root -> c	Create node for 'c' from root	root -> c
2	Insert 'cat' char 'a'	root -> c -> a	Create node for 'a' from 'c'	root -> c -> a
3	Insert 'cat' char 't'	root -> c -> a -> t (end)	Create node for 't' from 'a', mark end	root -> c -> a -> t*
4	Insert 'car' char 'c'	root -> c	Node 'c' exists, move to 'c'	root -> c
5	Insert 'car' char 'a'	root -> c -> a	Node 'a' exists, move to 'a'	root -> c -> a
6	Insert 'car' char 'r'	root -> c -> a -> t*, r (end)	Create node for 'r' from 'a', mark end	root -> c -> a -> t*, r*
7	Insert 'dog' char 'd'	root -> c, d	Create node for 'd' from root	root -> c, d
8	Insert 'dog' char 'o'	root -> c, d -> o	Create node for 'o' from 'd'	root -> c, d -> o
9	Insert 'dog' char 'g'	root -> c, d -> o -> g (end)	Create node for 'g' from 'o', mark end	root -> c, d -> o -> g*
10	Autocomplete 'ca' prefix traversal	root -> c -> a	Traverse root to 'c', then 'a'	root -> c -> a
11	DFS from 'a' node to find words	root -> c -> a -> t*, r*	Visit 't' and 'r' nodes marked end	Found words: 'cat', 'car'
12	Return autocomplete suggestions	N/A	Output ['cat', 'car']	Suggestions: ['cat', 'car']

💡 Autocomplete completes after collecting all words starting with prefix 'ca'

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 11	Final
Trie Nodes Count	0	4	6	9	9	9
Current Node	root	t (end of 'cat')	r (end of 'car')	g (end of 'dog')	a (prefix node)	a (prefix node)
Words Found	[]	[]	[]	[]	['cat', 'car']	['cat', 'car']

Key Moments - 3 Insights

Why do we mark the end of a word in the Trie?

Marking the end of a word (like 't' in 'cat') helps us know when a complete word finishes during traversal, as shown in steps 3, 6, and 9 in the execution_table.

Why do we traverse the Trie nodes for each character instead of the whole word at once?

We insert and traverse character by character to build and follow the path in the Trie, as seen in steps 1-3 for 'cat' and steps 10-11 for prefix 'ca'.

How do we find all words starting with a prefix?

After reaching the prefix node (step 10), we perform a depth-first search (DFS) to collect all words below it, as shown in step 11.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, which nodes exist under 'a'?

A 't' and 'r' nodes, both marked as end of words

B Only 't' node marked as end

C Only 'r' node marked as end

D No child nodes under 'a'

💡 Hint

Check the Visual State column at step 6 showing 't*' and 'r*' under 'a'

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

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look for when the 'g' node is created and marked as end (step 9)

If we change the prefix to 'do', what would the autocomplete suggestions be?

A ['cat', 'car']

B ['dog']

C []

D ['cat', 'car', 'dog']

💡 Hint

Refer to variable_tracker and execution_table steps 10-11 for prefix traversal and DFS

Concept Snapshot

Trie Autocomplete System:
- Insert words char by char into Trie nodes
- Mark nodes where words end
- For autocomplete, traverse prefix nodes
- DFS from prefix node to collect words
- Return all words starting with prefix

Full Transcript

This visualization shows how an autocomplete system uses a Trie data structure. Words like 'cat', 'car', and 'dog' are inserted one character at a time, creating nodes for each character. Nodes where words end are marked to identify complete words. When a user inputs a prefix like 'ca', the system traverses the Trie nodes for 'c' and 'a'. From the 'a' node, it performs a depth-first search to find all words starting with 'ca', which are 'cat' and 'car'. The execution table tracks each insertion and traversal step, showing how nodes are created and pointers move. The variable tracker shows the count of nodes, current traversal node, and words found at each step. Key moments clarify why marking word ends is important, why traversal is character by character, and how DFS collects autocomplete suggestions. The quiz tests understanding of Trie structure and traversal steps.