Word Search in Trie in DSA Rust

Mental Model

A trie is a tree where each path from root to a node spells a word. Searching means following letters step-by-step down the tree.

Analogy: Imagine a phone book organized by first letter, then second letter, and so on. To find a name, you open the section for the first letter, then the next, until you find the full name.

root
 ↓
[a]
 ↓
[p]
 ↓
[p]
 ↓
[l]
 ↓
[e] (word end)

Each arrow points to the next letter node.

Dry Run Walkthrough

Input: Insert words: "apple", "app"; Search for "app" and "appl"

Goal: Show how to find if a word exists by following nodes for each letter

Step 1: Start at root, look for 'a' child

root -> [a] -> p -> p -> l -> e (word end)

Why: We must find the first letter node to continue searching

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

root -> a -> [p] -> p -> l -> e (word end)

Why: Next letter must be found to continue the word path

Step 3: Move to first 'p', look for next 'p' child

root -> a -> p -> [p] -> l -> e (word end)

Why: Continue following letters in the word

Step 4: At second 'p', check if this node marks end of word for "app"

root -> a -> p -> p [word end] -> l -> e (word end)

Why: "app" is a word because this node marks word end

Step 5: For "appl", move to 'l' child of second 'p'

root -> a -> p -> p -> [l] -> e (word end)

Why: Check if 'l' node exists to continue search

Step 6: Check if 'l' node marks end of word

root -> a -> p -> p -> l [no word end] -> e (word end)

Why: "appl" is not a word because 'l' node is not word end

Result:

root -> a -> p -> p [word end] -> l -> e (word end)
"app" found: true
"appl" found: false

Annotated Code

DSA Rust

use std::collections::HashMap;

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

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

struct Trie {
    root: TrieNode,
}

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

    fn insert(&mut self, word: &str) {
        let mut curr = &mut self.root;
        for ch in word.chars() {
            curr = curr.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new())).as_mut(); // move or create child
        }
        curr.is_word_end = true; // mark end of word
    }

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

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

    println!("app found: {}", trie.search("app"));
    println!("appl found: {}", trie.search("appl"));
}

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

move to child node for current letter, create if missing

curr.is_word_end = true;

mark current node as end of a word

match curr.children.get(&ch) { ... }

check if next letter node exists to continue search

curr.is_word_end

return true if current node marks end of searched word

Output

app found: true

appl found: false

Complexity Analysis

Time: O(m) because we process each of the m letters in the word once during insert or search

Space: O(n*m) in worst case for n words each of length m, due to nodes created for unique prefixes

vs Alternative: Compared to searching in a list of words (O(n*m)), trie search is faster (O(m)) because it avoids scanning all words

Edge Cases

searching empty string

returns false because empty word is not inserted

DSA Rust

curr.is_word_end

searching word not inserted

returns false when a letter node is missing

DSA Rust

None => return false

searching prefix that is not a word

returns false because node exists but is_word_end is false

DSA Rust

curr.is_word_end

When to Use This Pattern

When you need to quickly check if words or prefixes exist in a large set, use a trie to follow letter paths efficiently.

Common Mistakes

Mistake: Not marking the end of word node, causing search to wrongly find prefixes as words
Fix: Set is_word_end = true at the last node of inserted word

Mistake: Not checking if child node exists before moving, causing runtime errors
Fix: Use safe lookup with get() and handle missing nodes by returning false

Summary

It stores words as paths in a tree and checks if a word exists by following letters step-by-step.

Use it when you want fast word or prefix searches in many words.

The key is to mark nodes where words end and follow nodes for each letter during search.

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