Word Search in Trie in DSA Rust - Execution Trace

Concept Flow - Word Search in Trie

Start at root node

↓

For each letter in word

↓

Check if letter child exists?

No→Word NOT found

Yes↓

Move to child node

↓

Repeat for next letter

↓

After last letter, check is_word flag

↓

If true: Word FOUND

The search starts at the root and moves down nodes matching each letter. If any letter is missing, the word is not found. At the end, the node must mark a complete word.

Execution Sample

DSA Rust

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

This function checks if a word exists in the trie by traversing nodes for each letter.

Execution Table

Step	Operation	Current Node Letter	Next Letter	Child Exists?	Move Pointer	Visual State
1	Start search	root	c	N/A	At root	[root]
2	Check child for 'c'	root	c	Yes	Move to 'c'	[root] -> [c]
3	Check child for 'a'	c	a	Yes	Move to 'a'	[root] -> [c] -> [a]
4	Check child for 't'	a	t	Yes	Move to 't'	[root] -> [c] -> [a] -> [t]
5	End of word	t	N/A	N/A	Check is_word	[root] -> [c] -> [a] -> [t*]
6	Result	t	N/A	N/A	Word found	Word 'cat' found

💡 Traversal ended after last letter; node marked as word end.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
node	root	node at 'c'	node at 'a'	node at 't'	node at 't'	node at 't'
current_letter	N/A	'c'	'a'	't'	N/A	N/A
is_word	N/A	N/A	N/A	N/A	true	true

Key Moments - 3 Insights

Why do we check if the child node exists before moving?

Because if the child node for the next letter does not exist (see Step 2-4 in execution_table), the word cannot be in the trie, so we stop searching.

Why do we check the is_word flag at the end?

Because the path might exist but not mark a complete word (Step 5). Only if is_word is true do we confirm the word is stored.

What happens if the word is empty?

The search starts and ends at root. Since root usually does not mark a word, the result is false immediately.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node letter at Step 3?

A 't'

B 'a'

C 'c'

D 'root'

💡 Hint

Check the 'Current Node Letter' column at Step 3 in execution_table.

At which step does the search confirm the word is found?

A Step 6

B Step 4

C Step 5

D Step 2

💡 Hint

Look at the 'Operation' and 'Result' columns in execution_table for when word found is stated.

If the child node for letter 'a' was missing, what would happen?

A Search marks word found anyway

B Search continues to next letter

C Search returns false immediately

D Search restarts from root

💡 Hint

Refer to 'Child Exists?' and 'Move Pointer' columns in execution_table Steps 2-4.

Concept Snapshot

Word Search in Trie:
- Start at root node
- For each letter, move to child node if exists
- If any letter missing, word not found
- After last letter, check is_word flag
- Return true if is_word is true, else false

Full Transcript

This visualization shows how to search a word in a trie data structure. We start at the root node and check each letter of the word in order. For each letter, we look for a child node matching that letter. If the child node exists, we move to it and continue. If at any point the child node does not exist, the word is not in the trie. After processing all letters, we check if the current node marks the end of a word. If yes, the word is found; otherwise, it is not. The execution table traces each step, showing the current node, letter checked, and pointer moves. The variable tracker shows how the node pointer and letters change. Key moments clarify why we check for child existence and the is_word flag. The quiz tests understanding of node positions and search outcomes.

Practice

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

easy

A. To sort words alphabetically

B. To store words in a hash table

C. To efficiently store and search words by their prefixes

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters in nodes where each path from root to a node represents a prefix of words.

2. Step 2: Purpose in word search

   This structure allows quick prefix checks and word searches, making it efficient for word search problems.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option C

4. Quick Check:

   Trie = Prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Confusing Trie with hash tables
• Thinking Trie sorts words
• Assuming Trie stores whole words only

2. Which of the following is the correct Rust syntax to define a Trie node struct with a children field as a vector of optional boxed Trie nodes?

easy

A. struct TrieNode { children: Vec> }

B. struct TrieNode { children: Vec<TrieNode> }

C. struct TrieNode { children: Option> }

D. struct TrieNode { children: Box> }

Solution

1. Step 1: Understand Rust ownership and pointers

   To allow recursive data structures, Rust uses Box to allocate on heap and Option for nullable children.

2. Step 2: Correct syntax for children field

   Children should be a vector of optional boxed TrieNode references: Vec>.

3. Final Answer:

   struct TrieNode { children: Vec> } -> Option A

4. Quick Check:

   Recursive struct uses Box and Option [OK]

Hint: Use Box and Option for recursive Trie nodes in Rust [OK]

Common Mistakes:

• Using Vec<TrieNode> causes infinite size error
• Wrapping Vec in Option instead of elements
• Incorrect Box placement

3. Given the following Rust code snippet for searching a word in a Trie, what will be the output printed?

struct TrieNode {
    children: Vec>,
    is_end: bool,
}

impl TrieNode {
    fn search(&self, word: &str) -> bool {
        let mut node = self;
        for ch in word.chars() {
            let index = (ch as usize) - ('a' as usize);
            match &node.children[index] {
                Some(child) => node = child,
                None => return false,
            }
        }
        node.is_end
    }
}

fn main() {
    let mut root = TrieNode {
        children: vec![None; 26],
        is_end: false,
    };
    println!("{}", root.search("cat"));
    println!("{}", root.search("car"));
}

medium

A. true
false

B. false
false

C. true
true

D. Compilation error

Solution

1. Step 1: Analyze search function behavior

   The search returns true if all characters are found and the last node marks end of a word.

2. Step 2: Check given calls

   No words are inserted; root.children initialized to vec![None; 26]. For "cat" and "car", first char 'c' (index 2) is None, so both return false.

3. Final Answer:

   false false -> Option B

4. Quick Check:

   Search returns false for non-inserted words [OK]

Hint: Search returns true only if full word exists [OK]

Common Mistakes:

• Assuming partial prefix returns true
• Ignoring is_end flag
• Confusing character indexing

4. Identify the bug in this Rust Trie search method and select the correct fix:

fn search(&self, word: &str) -> bool {
    let mut node = self;
    for ch in word.chars() {
        let index = (ch as usize) - ('a' as usize);
        if node.children[index].is_some() {
            node = &node.children[index].unwrap();
        } else {
            return false;
        }
    }
    true
}

medium

A. Return node.is_end instead of true at the end

B. Change unwrap() to expect() with error message

C. Use mutable reference for node variable

D. Initialize children vector with 26 None elements

Solution

1. Step 1: Understand search logic

   The method should return true only if the word ends at a node marked as end of a word.

2. Step 2: Identify bug in return statement

   Returning true always ignores if the node marks end of a word; must return node.is_end.

3. Final Answer:

   Return node.is_end instead of true at the end -> Option A

4. Quick Check:

   Search must check is_end flag [OK]

Hint: Always check is_end flag after traversal [OK]

Common Mistakes:

• Returning true without checking is_end
• Ignoring None cases
• Misusing unwrap without safety

5. You want to implement a function in Rust that searches for all words in a Trie starting with a given prefix. Which approach correctly combines Trie traversal and word collection?

hard

A. Use a hash map to map prefixes to words and lookup directly

B. Search each word in Trie individually to check prefix match

C. Store all words in a vector and filter by prefix using string starts_with

D. Traverse Trie nodes for prefix, then recursively collect all words from that node

Solution

1. Step 1: Traverse Trie for prefix

   Follow nodes for each character in prefix to reach prefix node.

2. Step 2: Collect words recursively

   From prefix node, recursively explore children to collect all complete words.

3. Final Answer:

   Traverse Trie nodes for prefix, then recursively collect all words from that node -> Option D

4. Quick Check:

   Prefix traversal + recursive collection = A [OK]

Hint: Find prefix node, then gather words recursively [OK]

Common Mistakes:

• Checking all words instead of prefix traversal
• Using external data structures unnecessarily
• Ignoring recursive collection after prefix