Trie Search Operation in DSA Rust

Mental Model

A trie stores words by branching letters step-by-step. Searching means following these letter branches to see if a word exists.

Analogy: Imagine a tree where each branch is a letter. To find a word, you walk down the branches matching each letter in order until you reach the end.

root
 ↓
 [c] -> [a] -> [t*]
        ↓
       [r] -> [s*]

* means end of a word

Dry Run Walkthrough

Input: Trie contains words: "cat", "cars"; search for "car"

Goal: Check if the word "car" exists in the trie

Step 1: Start at root node, look for child 'c'

root -> [c] -> [a] -> [t*]
               ↓
              [r] -> [s*]

Why: We must find the first letter 'c' to continue searching

Step 2: Move to node 'c', look for child 'a'

root -> c -> [a] -> [t*]
               ↓
              [r] -> [s*]

Why: Next letter 'a' must be found under 'c'

Step 3: Move to node 'a', look for child 'r'

root -> c -> a -> [t*]
               ↓
              [r] -> [s*]

Why: Next letter 'r' must be found under 'a'

Step 4: Move to node 'r', check if this node marks end of word

root -> c -> a -> r -> [s*]

Why: We reached last letter of search word; check if word ends here

Step 5: Node 'r' is not end of word, so 'car' is not in trie

root -> c -> a -> r -> s*

Why: Only 'cars' ends here, not 'car'

Result:

root -> c -> a -> r -> s*
Search result: false ("car" not found)

Annotated Code

DSA Rust

use std::collections::HashMap;

struct TrieNode {
    children: HashMap<char, Box<TrieNode>>,
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_end_of_word: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }

    fn insert(&mut self, word: &str) {
        let mut current = &mut self.root;
        for ch in word.chars() {
            current = current.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new()));
        }
        current.is_end_of_word = true;
    }

    fn search(&self, word: &str) -> bool {
        let mut current = &self.root;
        for ch in word.chars() {
            match current.children.get(&ch) {
                Some(node) => current = node, // advance to next letter node
                None => return false, // letter not found, word missing
            }
        }
        current.is_end_of_word // check if word ends here
    }
}

fn main() {
    let mut trie = Trie::new();
    trie.insert("cat");
    trie.insert("cars");

    let word = "car";
    let found = trie.search(word);
    println!("Search result for '{}': {}", word, found);
}

current = current.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new()));

advance current to child node for letter, create if missing

match current.children.get(&ch) {

check if next letter node exists to continue search

Some(node) => current = node, // advance to next letter node

move current pointer to next letter node

None => return false, // letter not found, word missing

stop search early if letter path missing

current.is_end_of_word // check if word ends here

confirm if current node marks end of searched word

Output

Search result for 'car': false

Complexity Analysis

Time: O(m) because we check each of the m letters in the search word once

Space: O(1) for search since no extra space besides pointers is used

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster as it directly follows letter branches

Edge Cases

search empty string

returns false because empty word is not stored

DSA Rust

current.is_end_of_word // check if word ends here

search word not in trie

returns false early when letter missing

DSA Rust

None => return false, // letter not found, word missing

search word is prefix of stored word but not marked end

returns false because is_end_of_word is false

DSA Rust

current.is_end_of_word // check if word ends here

When to Use This Pattern

When you need to quickly check if a word or prefix exists among many words, use the trie search pattern because it follows letter branches efficiently.

Common Mistakes

Mistake: Not checking if the current node marks the end of a word after traversing all letters
Fix: Always check the is_end_of_word flag at the last node to confirm full word presence

Mistake: Returning true as soon as all letters are found without verifying word end
Fix: Return true only if is_end_of_word is true at the last letter node

Summary

It checks if a word exists by following letter branches in the trie.

Use it when you want fast word lookups among many stored words.

The key is to follow each letter node and confirm the word ends exactly there.

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