Trie Search Operation in DSA Rust - Execution Trace

Concept Flow - Trie Search Operation

Start at root node

↓

Check current character in word

↓

Does child node for char exist?

No→Word NOT found, stop

Yes↓

Move pointer to child node

↓

More characters left?

Yes→Repeat check for next char

No↓

Is current node end of word?

Yes→Word FOUND

No↓

Word NOT found

The search starts at the root and checks each character of the word step-by-step. If a character's child node is missing, the word is not found. If all characters are found and the last node marks the end of a word, the search succeeds.

Execution Sample

DSA Rust

fn search(&self, word: &str) -> bool {
    let mut current = &self.root;
    for ch in word.chars() {
        if let Some(node) = current.children.get(&ch) {
            current = node;
        } else {
            return false;
        }
    }
    current.is_end_of_word
}

This code checks each character of the word in the trie nodes. If all characters are found and the last node marks the end of a word, it returns true; otherwise false.

Execution Table

Step	Operation	Current Character	Child Exists?	Pointer Moves To	Visual State
1	Start search at root	-	N/A	root	root node (empty)
2	Check 'c'	'c'	Yes	node_c	root → c
3	Check 'a'	'a'	Yes	node_a	root → c → a
4	Check 't'	't'	Yes	node_t	root → c → a → t
5	No more chars, check end flag	-	N/A	node_t	node_t.is_end_of_word = true
6	Result	-	-	-	Word FOUND
7	Start search at root	-	N/A	root	root node (empty)
8	Check 'c'	'c'	Yes	node_c	root → c
9	Check 'a'	'a'	Yes	node_a	root → c → a
10	Check 'r'	'r'	No	-	No child for 'r' at node_a
11	Result	-	-	-	Word NOT found

💡 Search stops when a character's child node is missing or after checking all characters and verifying end of word flag.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	node_c	node_a	node_t	node_t	node_t
current_char	-	'c'	'a'	't'	-	-
is_end_of_word	-	-	-	-	true	true

Key Moments - 3 Insights

Why does the search fail at step 10 when checking 'r'?

At step 10 in the execution_table, the child node for 'r' does not exist under node_a, so the search stops and returns false.

Why do we check the is_end_of_word flag after the last character?

At step 5, even if all characters are found, the word is only valid if the current node marks the end of a word. Otherwise, the search returns false.

What happens if the word is empty?

If the word is empty, the search starts and ends at the root. Usually, root.is_end_of_word is false, so the search returns false immediately.

Visual Quiz - 3 Questions

Look at the execution_table, what is the pointer position after checking character 'a' in the first search?

A node_a

B node_c

C node_t

D root

💡 Hint

Check row 3 in execution_table where current pointer moves to node_a after 'a'

At which step does the search fail for the word 'car'?

A Step 8

B Step 9

C Step 10

D Step 11

💡 Hint

Look at execution_table row 10 where child for 'r' does not exist

If the is_end_of_word flag was false at node_t in the first search, what would be the result?

A Word FOUND

B Word NOT found

C Search continues

D Error occurs

💡 Hint

Refer to step 5 and 6 in execution_table where is_end_of_word determines success

Concept Snapshot

Trie Search Operation:
- Start at root node
- For each character, move to child node if exists
- If child missing, word not found
- After last char, check is_end_of_word flag
- Return true if flag set, else false

Full Transcript

The Trie Search Operation starts at the root node and checks each character of the input word one by one. For each character, it looks for a child node in the current node's children. If the child node exists, the pointer moves to that node and continues. If at any point a child node for the current character does not exist, the search stops and returns false, meaning the word is not found. After all characters are checked, the search verifies if the current node marks the end of a word. If yes, it returns true; otherwise, false. This ensures only complete words stored in the trie are found, not prefixes.

Practice

1. What does the search operation in a Trie data structure do?

easy

A. Counts the total words stored in the Trie

B. Inserts a new word into the Trie

C. Checks if a given word exists in the Trie

D. Deletes a word from the Trie

Solution

1. Step 1: Understand the purpose of search in Trie

   The search operation is designed to check if a specific word is present in the Trie structure.

2. Step 2: Differentiate from other operations

   Insertion adds words, deletion removes words, and counting totals words, but search only checks existence.

3. Final Answer:

   Checks if a given word exists in the Trie -> Option C

4. Quick Check:

   Search = Check existence [OK]

Hint: Search checks presence, not insertion or deletion [OK]

Common Mistakes:

• Confusing search with insert operation
• Thinking search deletes words
• Assuming search counts words

2. Which of the following is the correct Rust function signature for a Trie search method that returns a boolean?

easy

A. fn search(&self, word: &str) -> bool

B. fn search(word: String) -> bool

C. fn search(&mut self, word: &str) -> String

D. fn search(&self, word: &str) -> usize

Solution

1. Step 1: Identify correct method receiver and parameters

   The search method should borrow self immutably (&self) and take a string slice (&str) for the word to search.

2. Step 2: Confirm return type

   Search returns a boolean indicating presence, so return type must be bool.

3. Final Answer:

   fn search(&self, word: &str) -> bool -> Option A

4. Quick Check:

   Immutable borrow + &str + bool return [OK]

Hint: Search uses &self and returns bool [OK]

Common Mistakes:

• Using mutable borrow &mut self unnecessarily
• Returning wrong type like String or usize
• Taking owned String instead of &str

3. Given the following Rust Trie search code snippet, what will be the output when searching for "cat"?

let mut trie = Trie::new();
trie.insert("car");
trie.insert("cat");
trie.insert("cap");
println!("{}", trie.search("cat"));

medium

A. Compilation error

B. false

C. panic at runtime

D. true

Solution

1. Step 1: Analyze inserted words

   The words "car", "cat", and "cap" are inserted into the Trie, so "cat" is present.

2. Step 2: Check search output for "cat"

   Searching "cat" should return true because it was inserted.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Inserted words include "cat" so search returns true [OK]

Hint: Search returns true if word was inserted [OK]

Common Mistakes:

• Assuming search returns false if similar words exist
• Confusing insert and search methods
• Expecting runtime errors without reason

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

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

medium

A. Uses unwrap() which causes panic always

B. Returns true even if word is a prefix but not complete word

C. Does not iterate over characters correctly

D. Incorrect return type

Solution

1. Step 1: Understand search logic

   The code checks if each character exists in children nodes, moving down the Trie.

2. Step 2: Check final return condition

   It returns true after loop without verifying if current node marks end of a complete word.

3. Step 3: Identify bug

   This causes search to return true for prefixes that are not full words.

4. Final Answer:

   Returns true even if word is a prefix but not complete word -> Option B

5. Quick Check:

   Missing end-of-word check causes false positives [OK]

Hint: Check end-of-word flag after traversal [OK]

Common Mistakes:

• Ignoring end-of-word marker in search
• Assuming unwrap() always panics here
• Misunderstanding iteration over chars

5. You want to modify a Trie search operation in Rust to support searching with wildcard character '.' which can match any single letter. Which approach is best to implement this feature?

hard

A. Use recursion to explore all children nodes when '.' is encountered

B. Replace '.' with all alphabets before searching iteratively

C. Ignore '.' and treat it as a normal character

D. Use a hash map to store wildcard positions and skip them

Solution

1. Step 1: Understand wildcard '.' meaning

   The '.' can match any single character, so search must consider all possible children at that position.

2. Step 2: Choose search strategy

   Recursion allows exploring all children nodes when '.' is found, checking all paths.

3. Step 3: Evaluate other options

   Replacing '.' with all alphabets is inefficient; ignoring '.' is incorrect; hash map for positions doesn't solve matching.

4. Final Answer:

   Use recursion to explore all children nodes when '.' is encountered -> Option A

5. Quick Check:

   Recursion handles wildcards by branching [OK]

Hint: Use recursion to handle '.' wildcard in search [OK]

Common Mistakes:

• Ignoring wildcard meaning
• Trying to replace '.' with all letters before search
• Skipping recursive exploration