Word Search in Trie in DSA Rust - Time & Space Complexity

Time Complexity: Word Search in Trie

O(n)

Understanding Time Complexity

We want to understand how long it takes to find a word in a Trie data structure.

The question is: how does the search time grow as the word length or Trie size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct TrieNode {
    children: [Option; 26],
    is_end: bool,
}

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

This code searches for a word in a Trie by checking each character one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each character in the input word.
• How many times: Exactly once per character in the word (word length).

How Execution Grows With Input

As the word gets longer, the search checks more characters one after another.

Input Size (n = word length)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The number of steps grows directly with the word length.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows linearly with the length of the word you want to find.

Common Mistake

[X] Wrong: "Searching a word in a Trie depends on the total number of words stored."

[OK] Correct: The search only depends on the length of the word being searched, not how many words are in the Trie.

Interview Connect

Knowing how Trie search scales helps you explain why Tries are efficient for prefix and word lookups.

This skill shows you understand how data structure design affects performance.

Self-Check

"What if we changed the search to allow wildcards that match any character? How would the time complexity change?"

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