Prefix Search Using Trie in DSA Rust - Execution Trace

Concept Flow - Prefix Search Using Trie

Start at root node

↓

For each character in prefix

↓

Check if child node exists

↓

Move to child

↓

After last char

↓

Collect all words below

↓

Return matched words

Start from the root, follow each prefix character down the trie nodes. If any character node is missing, prefix not found. Otherwise, collect all words below the last node.

Execution Sample

DSA Rust

insert("cat")
insert("car")
insert("dog")
search_prefix("ca")

Insert words 'cat', 'car', 'dog' into trie, then search for words starting with prefix 'ca'.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat'	root -> c -> a -> t	root.children['c'] created c.children['a'] created a.children['t'] created (end of word)	root └─ c └─ a └─ t*
2	Insert 'car'	root -> c -> a -> t, r	Reuse root->c->a Add a.children['r'] created (end of word)	root └─ c └─ a ├─ t* └─ r*
3	Insert 'dog'	root -> c -> a -> t, r; d -> o -> g	root.children['d'] created d.children['o'] created o.children['g'] created (end of word)	root ├─ c │ └─ a │ ├─ t* │ └─ r* └─ d └─ o └─ g*
4	Search prefix 'ca'	No change	Traverse root->c->a	At node 'a' with children t*, r*
5	Collect words under 'a'	No change	Collect 'cat', 'car'	Matched words: ['cat', 'car']
6	Search prefix 'do'	No change	Traverse root->d->o	At node 'o' with child g*
7	Collect words under 'o'	No change	Collect 'dog'	Matched words: ['dog']
8	Search prefix 'cae'	No change	Traverse root->c->a->e fails (no 'e' child)	Prefix not found

💡 Search stops when prefix character node missing or all prefix chars traversed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8
Trie Nodes	root (empty)	root, c, a, t*	root, c, a, t*, r*	root, c, a, t*, r*, d, o, g*	No change	No change	No change	No change	No change
Current Node	root	root	root	root	node 'a'	node 'a'	node 'o'	node 'o'	null (prefix not found)
Matched Words	[]	[]	[]	[]	[]	['cat', 'car']	[]	['dog']	[]

Key Moments - 3 Insights

Why do we stop searching if a prefix character node is missing?

Because the trie does not contain any word starting with that prefix. See execution_table step 8 where 'e' child is missing after 'a', so search stops.

How do we collect all words after reaching the last prefix node?

We do a traversal (like DFS) from that node collecting all words marked as end of word. See execution_table steps 5 and 7 where words under 'a' and 'o' nodes are collected.

Why do we reuse existing nodes when inserting new words?

To save space and share common prefixes. For example, 'cat' and 'car' share nodes root->c->a. See execution_table step 2 where 'r' is added under existing 'a'.

Visual Quiz - 3 Questions

Look at the execution_table, what nodes exist after inserting 'car' (step 2)?

A root -> d -> o -> g

B root -> c -> a -> t only

C root -> c -> a -> t, r

D root -> c -> r

💡 Hint

Check execution_table row for step 2 under 'Nodes in Trie' and 'Visual State'

At which step does the search fail due to missing prefix node?

A Step 6

B Step 8

C Step 4

D Step 5

💡 Hint

Look at execution_table step 8 where traversal fails at 'e' child

If we search prefix 'do', what matched words do we get?

A ['dog']

B ['cat', 'car']

C []

D ['do']

💡 Hint

See execution_table step 7 'Collect words under o' shows matched words

Concept Snapshot

Prefix Search Using Trie:
- Start at root node
- For each prefix char, move to child node
- If child missing, prefix not found
- After last char, collect all words below
- Efficient for prefix-based word search

Full Transcript

This visual trace shows how prefix search works using a trie data structure. We insert words 'cat', 'car', and 'dog' step-by-step, creating nodes for each character. When searching for a prefix like 'ca', we follow nodes 'c' then 'a'. If all prefix characters exist, we collect all words below that node, such as 'cat' and 'car'. If a prefix character node is missing, like 'e' after 'a' in 'cae', the search stops with no matches. The trie shares nodes for common prefixes to save space. This step-by-step trace helps understand how prefix search efficiently finds all words starting with a given prefix.

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To efficiently find all words that start with a given prefix

B. To sort words alphabetically

C. To store numbers in sorted order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand Trie usage

   A Trie stores strings in a tree-like structure where each node represents a character, making prefix searches efficient.

2. Step 2: Identify prefix search goal

   Prefix search requires finding all words starting with a given prefix, which Trie supports directly by traversing nodes.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option A

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie is for numeric operations
• Assuming Trie stores full words only at root

2. Which of the following Rust code snippets correctly defines a Trie node struct for prefix search?

easy

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

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

C. struct TrieNode { children: String, is_end: bool }

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

Solution

1. Step 1: Check children type for TrieNode

   Children must map characters to child nodes, so HashMap is correct for recursive structure without size issues.

2. Step 2: Validate other options

   Vec<char> or String cannot map characters to nodes; i32 is invalid for children.

3. Final Answer:

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

4. Quick Check:

   Children map chars to nodes = struct TrieNode { children: HashMap, is_end: bool } [OK]

Hint: Use HashMap for children in Rust Trie [OK]

Common Mistakes:

• Using Vec<char> instead of mapping to nodes
• Using String for children instead of node references
• Using primitive types like i32 for children

3. Given the following Rust code snippet for inserting words into a Trie and searching for prefix "ca":

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

What will be printed?

medium

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

B. ["cat", "car"]

C. ["dog"]

D. []

Solution

1. Step 1: Insert words into Trie

   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: Prefix search returns words starting exactly with given prefix [OK]

Common Mistakes:

• Including words without the prefix
• Returning empty list if prefix exists
• Confusing prefix search with full word search

4. Consider this Rust code snippet for prefix search in a Trie:

fn starts_with(&self, prefix: &str) -> bool {
    let mut node = &self.root;
    for ch in prefix.chars() {
        if !node.children.contains_key(&ch) {
            return false;
        }
        node = node.children.get(&ch).unwrap();
    }
    true
}

What is the main issue with this code snippet?

medium

A. Cannot assign &TrieNode to node because of lifetime mismatch

B. Missing mutable keyword for node variable

C. Using unwrap() without checking Option

D. Incorrect return type for starts_with function

Solution

1. Step 1: Analyze function purpose

   This implements prefix existence check (returns bool).

2. Step 2: Identify mismatch for prefix search

   Prefix search requires returning all words with the prefix (e.g. Vec<String>), not just bool.

3. Final Answer:

   Incorrect return type for starts_with function -> Option D

4. Quick Check:

   Prefix search needs Vec<String> not bool [OK]

Hint: Verify return type matches prefix search requirements [OK]

Common Mistakes:

• Confusing prefix existence (bool) with full prefix search (list)
• Assuming unwrap() causes runtime error here
• Forgetting Rust borrow checker rules

5. You want to extend a Trie in Rust to support prefix search that returns all words starting with a prefix, but also limit results to a maximum of 2 words. Which approach is best?

hard

A. Use a HashSet to store all words and filter after search

B. Store only 2 words per node during insertion

C. Modify DFS traversal to stop collecting words after 2 matches

D. Return only the first word found with the prefix

Solution

1. Step 1: Understand prefix search with limit

   We want to find all words starting with prefix but stop after 2 matches to save time.

2. Step 2: Modify DFS traversal

   During DFS from prefix node, keep count of collected words and stop recursion once 2 words are found.

3. Step 3: Evaluate other options

   Storing only 2 words per node loses data; filtering after search is inefficient; returning one word is incomplete.

4. Final Answer:

   Modify DFS traversal to stop collecting words after 2 matches -> Option C

5. Quick Check:

   Limit results by stopping DFS early [OK]

Hint: Stop DFS early to limit prefix search results [OK]

Common Mistakes:

• Limiting stored words per node loses data
• Filtering after full search wastes time
• Returning only one word ignores requirement