Autocomplete System with Trie in DSA Rust - Execution Trace

Concept Flow - Autocomplete System with Trie

Start: Insert words into Trie

↓

For each word: For each char

↓

Check if char node exists?

No→Create new node

Yes↓

Move to next char node

↓

Mark end of word

↓

User types prefix

↓

Traverse Trie for prefix chars

↓

Collect all words from prefix node

↓

Return autocomplete suggestions

↓

End

Insert words character by character into the Trie, then traverse the Trie for the typed prefix to find all matching autocomplete suggestions.

Execution Sample

DSA Rust

struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    is_end: bool,
}

// Insert "cat" and "car" into Trie
// Then autocomplete for prefix "ca"

This code inserts words into a Trie and then finds autocomplete suggestions for a given prefix.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat' char 'c'	Root -> c	Create node for 'c' under root	root -> c -> null
2	Insert 'cat' char 'a'	Root -> c -> a	Create node for 'a' under 'c'	root -> c -> a -> null
3	Insert 'cat' char 't'	Root -> c -> a -> t	Create node for 't' under 'a', mark end	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 for 'r' under 'a', mark end	root -> c -> a -> t*, r*
7	Autocomplete prefix 'ca' char 'c'	Root -> c -> a -> t*, r*	Move to node 'c'	root -> c -> a -> t*, r*
8	Autocomplete prefix 'ca' char 'a'	Root -> c -> a -> t*, r*	Move to node 'a'	root -> c -> a -> t*, r*
9	Collect words from node 'a'	Root -> c -> a -> t*, r*	Traverse children 't' and 'r' nodes	Suggestions: 'cat', 'car'
10	Return suggestions	Root -> c -> a -> t*, r*	Output ['cat', 'car']	Done

💡 All prefix characters processed and suggestions collected.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	After Step 9	Final
Trie Root	Empty	Has child 'c'	Has path c->a->t*	Has path c->a->t*, r*	Same	Same
Current Node	Root	'c' node	't' node (end of 'cat')	'r' node (end of 'car')	'a' node (prefix end)	'a' node
Suggestions List	Empty	Empty	Empty	Empty	['cat', 'car']	['cat', 'car']

Key Moments - 3 Insights

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

Because if the node exists, it means that prefix is already stored, so we just move forward. See steps 4 and 5 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 with a flag (is_end). In step 3 and 6, nodes 't' and 'r' are marked as word ends.

How does the autocomplete collect all words from a prefix node?

It traverses all child nodes recursively from the prefix node, collecting words at nodes marked as word ends. Step 9 shows traversal from node 'a' to 't' and 'r' nodes.

Visual Quiz - 3 Questions

Look at the execution table at step 3, which node is marked as the end of the word?

A 'a' node

B 't' node

C 'c' node

D 'r' node

💡 Hint

Check the 'Visual State' column at step 3 showing 't*' means end of word.

At which step does the Trie first contain two different word endings under the same prefix?

A Step 9

B Step 3

C Step 6

D Step 1

💡 Hint

Look at 'Nodes in Trie' column; step 6 shows both 't*' and 'r*' under 'a'.

If we change the prefix to 'car', at which step would the autocomplete traversal stop?

A Step 9

B Step 7

C Step 8

D Step 10

💡 Hint

Autocomplete traversal stops after processing all prefix characters; see steps 7-9 for prefix 'ca'.

Concept Snapshot

Autocomplete with Trie:
- Insert words char by char, create nodes if missing
- Mark last char node as word end
- For prefix, traverse Trie nodes
- Collect all words from prefix node recursively
- Efficient prefix search for autocomplete

Full Transcript

This visualization shows how an autocomplete system uses a Trie data structure. Words are inserted character by character, creating new nodes only if they don't exist. The last character node of each word is marked to indicate word end. When a user types a prefix, the Trie is traversed for each character of the prefix. From the last prefix node, all child nodes are explored to collect complete words as suggestions. The execution table traces each insertion and traversal step, showing how nodes are created and pointers move. Key moments clarify why nodes are created conditionally, how word ends are marked, and how suggestions are gathered. The quiz tests understanding of node marking, word endings, and traversal stopping points.

Practice

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

easy

A. To sort words alphabetically

B. To count the total number of words

C. To efficiently store and search prefixes of words

D. To reverse the input strings

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 quick prefix-based searches.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires finding all words starting with a given prefix efficiently, which a Trie supports well.

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 search [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie counts words only
• Assuming Trie reverses strings

2. Which of the following is the correct Rust syntax to define a Trie node struct with children as a HashMap and an is_end boolean?

easy

A. struct TrieNode { children: HashMap, is_end: bool }

B. struct TrieNode { children: HashMap, is_end: bool }

C. struct TrieNode { children: Vec<char>, is_end: bool }

D. struct TrieNode { children: HashMap, is_end: bool }

Solution

1. Step 1: Understand Rust ownership and recursive types

   Rust requires recursive types like TrieNode to use pointers such as Box to avoid infinite size errors.

2. Step 2: Check each option's children type

   struct TrieNode { children: HashMap, is_end: bool } uses HashMap, which is correct for recursive Trie nodes. struct TrieNode { children: HashMap, is_end: bool } lacks Box, causing compile error. struct TrieNode { children: Vec<char>, is_end: bool } uses Vec<char>, which is incorrect for children mapping. struct TrieNode { children: HashMap, is_end: bool } uses HashMap, which is incorrect because keys should be single chars.

3. Final Answer:

   struct TrieNode { children: HashMap, is_end: bool } -> Option A

4. Quick Check:

   Recursive struct needs Box pointer [OK]

Hint: Use Box for recursive struct fields in Rust [OK]

Common Mistakes:

• Omitting Box causes compile errors
• Using Vec instead of HashMap for children
• Using String keys instead of char

3. Given the following Rust code snippet for inserting words into a Trie, what will be the output of searching for prefix "ca"?

let mut trie = Trie::new();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
let results = trie.search_prefix("ca");
println!("{:?}", results);

medium

A. ["dog"]

B. ["cat", "car"]

C. ["cat"]

D. []

Solution

1. Step 1: Insert words into Trie

   The words "cat", "car", and "dog" are inserted. "cat" and "car" share prefix "ca".

2. Step 2: Search for prefix "ca"

   Searching prefix "ca" returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   ["cat", "car"] -> Option B

4. Quick Check:

   Prefix "ca" matches "cat", "car" [OK]

Hint: Search prefix returns all words starting with it [OK]

Common Mistakes:

• Returning only one matching word
• Returning words without the prefix
• Returning empty list incorrectly

4. Identify the bug in this Rust Trie insertion method snippet:

fn insert(&mut self, word: &str) {
    let mut node = &self.root;
    for ch in word.chars() {
        node = node.children.entry(ch).or_insert(TrieNode::new());
    }
    node.is_end = true;
}

medium

A. word.chars() should be collected into a vector first

B. Use of entry() is incorrect for insertion

C. is_end should be set before the loop

D. node should be mutable reference (&mut) to modify children

Solution

1. Step 1: Analyze mutability of node reference

   node is assigned as immutable reference &self.root, but children need to be modified, so node must be mutable reference &mut.

2. Step 2: Understand why mutability is needed for entry()

   entry() modifies the HashMap, so node must be mutable to call entry() and insert new nodes.

3. Final Answer:

   node should be mutable reference (&mut) to modify children -> Option D

4. Quick Check:

   Mutable reference needed for insertion [OK]

Hint: Use &mut to modify Trie nodes during insertion [OK]

Common Mistakes:

• Using immutable reference for mutable operations
• Setting is_end too early
• Unnecessary collection of chars

5. You want to extend a Trie-based autocomplete system to return suggestions sorted by frequency of word usage. Which data structure modification is best to support this efficiently?

hard

A. Store a frequency count at each end node and use a max-heap during search

B. Store words in a vector and sort on every search

C. Use a linked list to store words in insertion order

D. Store frequency counts but ignore them during search

Solution

1. Step 1: Understand frequency storage in Trie nodes

   Storing frequency counts at end nodes tracks how often each word is used.

2. Step 2: Use max-heap to retrieve top frequent words efficiently

   During prefix search, a max-heap can quickly select highest frequency words without sorting all results.

3. Final Answer:

   Store a frequency count at each end node and use a max-heap during search -> Option A

4. Quick Check:

   Frequency + max-heap = efficient top suggestions [OK]

Hint: Use frequency counts + max-heap for fast top suggestions [OK]

Common Mistakes:

• Sorting all words on every search (slow)
• Ignoring frequency data
• Using linked list which is inefficient for sorting