Trie Search Operation in DSA Rust - Build from Scratch

Trie Search Operation

📖 Scenario: You are building a simple word dictionary search tool. You want to store words so you can quickly check if a word exists in your dictionary.

🎯 Goal: Build a Trie data structure and implement a search operation to check if a given word is present in the Trie.

📋 What You'll Learn

Create a TrieNode struct with children and end_of_word flag

Create a Trie struct with a root node

Implement insert method to add words to the Trie

Implement search method to check if a word exists in the Trie

Test the search method with a sample word

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and IP routing to quickly find words or prefixes.

💼 Career

Understanding Trie search operations is important for software engineers working on search engines, text processing, and network routing.

1

Create the TrieNode struct

Create a struct called TrieNode with a field children as a vector of 26 Option elements and a boolean field end_of_word set to false.

DSA Rust

# Define the TrieNode struct
// Your code here

Hint

Think of children as 26 slots for each letter a-z. Use Option to allow empty or filled slots.

2

Create the Trie struct with root node

Create a struct called Trie with a field root of type TrieNode. Implement a new method for Trie that initializes root with TrieNode::new().

DSA Rust

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

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: vec![None; 26],
            end_of_word: false,
        }
    }
}

// Define the Trie struct and new method
// Your code here

Hint

The Trie holds the starting point root which is an empty TrieNode.

3

Implement the search method for Trie

Inside the impl Trie block, implement a method search that takes &self and a word: &str. Use a variable node starting at &self.root. For each character in word, calculate its index as (c as usize) - ('a' as usize). If node.children[index] is None, return false. Otherwise, update node to the child node. After the loop, return node.end_of_word.

DSA Rust

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

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: vec![None; 26],
            end_of_word: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

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

// Implement the search method below
// Your code here

Hint

Traverse the Trie nodes for each letter. If any letter is missing, return false. At the end, check if the node marks the end of a word.

4

Test the search method with a sample word

Create a main function. Inside it, create a Trie instance called trie using Trie::new(). Manually set trie.root.children[0] to Some(Box::new(TrieNode::new())) and mark trie.root.children[0].as_mut().unwrap().end_of_word as true to simulate the word "a" inserted. Then print the result of trie.search("a") and trie.search("b").

DSA Rust

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

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: vec![None; 26],
            end_of_word: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

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

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

fn main() {
    // Your code here
}

Hint

Manually add the word "a" by setting the first child and marking end_of_word true. Then test search for "a" and "b".

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