Word Search in Trie in DSA Rust - Build from Scratch

Word Search in Trie

📖 Scenario: You are building a simple word search tool for a small dictionary. You want to quickly check if a word exists in your dictionary using a Trie data structure.

🎯 Goal: Build a Trie, insert some words, and then search for a specific word to check if it exists.

📋 What You'll Learn

Create a TrieNode struct with children and end_of_word flag

Create a Trie struct with insert and search methods

Insert given words into the Trie

Search for a given word in the Trie

Print whether the word exists or not

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete features, spell checkers, and dictionary lookups to quickly find words.

💼 Career

Understanding Tries helps in roles involving text processing, search engines, and efficient data retrieval.

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 with children and end_of_word
# 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 insert method

Create a struct called Trie with a field root of type TrieNode. Then add an insert method that takes &mut self and a word: &str, and inserts the word into the Trie.

DSA Rust

struct Trie {
    root: TrieNode,
}

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

    // Add insert method here
    // Your code here
}

Hint

Use a mutable reference to traverse the Trie. Calculate the index by subtracting 'a' from the character.

3

Add the search method to Trie

Add a method called search to Trie that takes &self and a word: &str, and returns bool indicating if the word exists in the Trie.

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 insert(&mut self, word: &str) {
        let mut current = &mut self.root;
        for ch in word.chars() {
            let index = (ch as usize) - ('a' as usize);
            if current.children[index].is_none() {
                current.children[index] = Some(Box::new(TrieNode::new()));
            }
            current = current.children[index].as_mut().unwrap();
        }
        current.end_of_word = true;
    }

    // Add search method here
    // Your code here
}

Hint

Traverse the Trie like in insert, but do not create nodes. Return false if missing, else return end_of_word flag.

4

Insert words and search for a word, then print result

Create a mutable Trie called trie. Insert the words "apple", "app", and "bat" into trie. Then search for the word "app" and print "Found" if it exists or "Not Found" if it does not.

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 insert(&mut self, word: &str) {
        let mut current = &mut self.root;
        for ch in word.chars() {
            let index = (ch as usize) - ('a' as usize);
            if current.children[index].is_none() {
                current.children[index] = Some(Box::new(TrieNode::new()));
            }
            current = current.children[index].as_mut().unwrap();
        }
        current.end_of_word = true;
    }

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

fn main() {
    // Create a mutable Trie called trie
    // Insert "apple", "app", and "bat" into trie
    // Search for "app" and print "Found" if true else "Not Found"
    // Your code here
}

Hint

Use let mut trie = Trie::new(); to create the Trie. Use insert to add words. Use search to check and print the result.

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