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.

Practice

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

easy

A. To encrypt the stored words

B. To sort words alphabetically

C. To efficiently store and search prefixes of words

D. To count the total number of words

Solution

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

   A Trie is a tree-like data structure that stores characters of words in a way that common prefixes share nodes.

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 C

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie stores prefixes for fast autocomplete lookup [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with encryption methods
• Assuming Trie counts total words only

2. Which of the following is the correct way to declare a Trie node struct in Go?

easy

A. type TrieNode struct { children []int; isEnd int }

B. type TrieNode struct { children map[rune]*TrieNode; isEnd bool }

C. type TrieNode struct { children map[string]int; isEnd string }

D. type TrieNode struct { children []string; isEnd bool }

Solution

1. Step 1: Identify correct data types for TrieNode fields

   Children should map characters (rune) to child nodes (pointer to TrieNode). isEnd should be a boolean indicating word end.

2. Step 2: Match with given options

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } uses map[rune]*TrieNode and bool for isEnd, which is correct for Trie implementation in Go.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } -> Option B

4. Quick Check:

   Children map[rune]*TrieNode and bool isEnd [OK]

Hint: Children map keys are runes, values are pointers to TrieNode [OK]

Common Mistakes:

• Using slices instead of maps for children
• Using incorrect types like int or string for isEnd
• Mapping children with wrong key or value types

3. What will be the output of the following Go code snippet that inserts words into a Trie and searches for prefix "app"?

trie := NewTrie()
trie.Insert("apple")
trie.Insert("app")
trie.Insert("application")
results := trie.SearchPrefix("app")
fmt.Println(results)

Assuming SearchPrefix returns all words starting with the prefix.

medium

A. []

B. ["apple", "application"]

C. ["app"]

D. ["app", "apple", "application"]

Solution

1. Step 1: Insert words into Trie

   Words "apple", "app", and "application" are inserted, all sharing prefix "app".

2. Step 2: Search for prefix "app"

   SearchPrefix returns all words starting with "app", so it returns all three inserted words.

3. Final Answer:

   ["app", "apple", "application"] -> Option D

4. Quick Check:

   All words with prefix "app" returned [OK]

Hint: SearchPrefix returns all words starting with given prefix [OK]

Common Mistakes:

• Returning only exact prefix word
• Missing some words sharing prefix
• Returning empty list incorrectly

4. Identify the bug in this Go code snippet for inserting a word into a Trie:

func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{}
        }
        node = node.children[ch]
    }
    node.isEnd = false
}

medium

A. isEnd should be set to true after insertion

B. children map is not initialized

C. Loop variable ch should be int, not rune

D. Function should return a value

Solution

1. Step 1: Review isEnd assignment after insertion

   After inserting a word, isEnd should mark the node as end of a word, so it must be set to true.

2. Step 2: Check other parts of code

   children map initialization and loop variable type are correct; function does not need to return a value.

3. Final Answer:

   isEnd should be set to true after insertion -> Option A

4. Quick Check:

   isEnd = true after insert [OK]

Hint: Set isEnd true to mark word end [OK]

Common Mistakes:

• Setting isEnd to false instead of true
• Not initializing children map before use
• Expecting Insert to return a value

5. Given a Trie storing words, how can you modify the autocomplete system to return suggestions sorted by frequency of word usage?

hard

A. Store a frequency count at each end node and sort results by this count

B. Sort all words alphabetically before insertion

C. Use a separate array to store frequencies unrelated to Trie

D. Ignore frequency and return words in insertion order

Solution

1. Step 1: Add frequency tracking in Trie nodes

   Modify Trie nodes to store frequency count at nodes marking word ends to track usage.

2. Step 2: Sort autocomplete results by frequency

   When returning suggestions, sort collected words by their stored frequency counts to prioritize popular words.

3. Final Answer:

   Store a frequency count at each end node and sort results by this count -> Option A

4. Quick Check:

   Frequency count in Trie nodes enables sorted suggestions [OK]

Hint: Track frequency in nodes, sort suggestions by count [OK]

Common Mistakes:

• Sorting words before insertion does not help frequency
• Using unrelated arrays breaks Trie efficiency
• Ignoring frequency loses popular word priority