Prefix Search Using Trie in DSA Rust - Time & Space Complexity

Time Complexity: Prefix Search Using Trie

O(m)

Understanding Time Complexity

We want to understand how fast we can find words that start with a given prefix using a Trie.

How does the search time change as the prefix length or dictionary size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct TrieNode {
    children: std::collections::HashMap<char, std::boxed::Box<TrieNode>>,
    is_end: bool,
}

impl TrieNode {
    fn starts_with(&self, prefix: &str) -> bool {
        let mut node = self;
        for ch in prefix.chars() {
            if let Some(next) = node.children.get(&ch) {
                node = next;
            } else {
                return false;
            }
        }
        true
    }
}
    

This code checks if any word in the Trie starts with the given prefix by walking down the Trie nodes.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the prefix string.
• How many times: Exactly once per character in the prefix (length m).

How Execution Grows With Input

As the prefix gets longer, the search takes more steps, one per character.

Input Size (prefix length m)	Approx. Operations
10	10 lookups in children maps
100	100 lookups in children maps
1000	1000 lookups in children maps

Pattern observation: The time grows linearly with the prefix length, not with the total number of words stored.

Final Time Complexity

Time Complexity: O(m)

This means the search time depends only on the prefix length, not on how many words are in the Trie.

Common Mistake

[X] Wrong: "Searching a prefix takes time proportional to the total number of words stored."

[OK] Correct: The Trie lets us jump directly down the prefix path, so the search depends only on prefix length, not total words.

Interview Connect

Understanding prefix search time helps you explain why Tries are efficient for autocomplete and dictionary lookups.

Self-Check

"What if the children were stored in a fixed-size array instead of a HashMap? How would the time complexity change?"

Practice

1. What is the main purpose of using a Trie data structure in prefix search?

easy

A. To efficiently find all words that start with a given prefix

B. To sort words alphabetically

C. To store numbers in sorted order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand Trie usage

   A Trie stores strings in a tree-like structure where each node represents a character, making prefix searches efficient.

2. Step 2: Identify prefix search goal

   Prefix search requires finding all words starting with a given prefix, which Trie supports directly by traversing nodes.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option A

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie is for numeric operations
• Assuming Trie stores full words only at root

2. Which of the following Rust code snippets correctly defines a Trie node struct for prefix search?

easy

A. struct TrieNode { children: HashMap, is_end: bool }

B. struct TrieNode { children: Vec<char>, is_end: bool }

C. struct TrieNode { children: String, is_end: bool }

D. struct TrieNode { children: i32, is_end: bool }

Solution

1. Step 1: Check children type for TrieNode

   Children must map characters to child nodes, so HashMap is correct for recursive structure without size issues.

2. Step 2: Validate other options

   Vec<char> or String cannot map characters to nodes; i32 is invalid for children.

3. Final Answer:

   struct TrieNode { children: HashMap, is_end: bool } -> Option A

4. Quick Check:

   Children map chars to nodes = struct TrieNode { children: HashMap, is_end: bool } [OK]

Hint: Use HashMap for children in Rust Trie [OK]

Common Mistakes:

• Using Vec<char> instead of mapping to nodes
• Using String for children instead of node references
• Using primitive types like i32 for children

3. Given the following Rust code snippet for inserting words into a Trie and searching for prefix "ca":

let mut trie = Trie::new();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
let result = trie.starts_with("ca");
println!("{:?}", result);

What will be printed?

medium

A. ["cat", "car", "dog"]

B. ["cat", "car"]

C. ["dog"]

D. []

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted. "cat" and "car" share prefix "ca".

2. Step 2: Search for prefix "ca"

   Searching prefix "ca" returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   ["cat", "car"] -> Option B

4. Quick Check:

   Prefix "ca" matches cat, car [OK]

Hint: Prefix search returns words starting exactly with given prefix [OK]

Common Mistakes:

• Including words without the prefix
• Returning empty list if prefix exists
• Confusing prefix search with full word search

4. Consider this Rust code snippet for prefix search in a Trie:

fn starts_with(&self, prefix: &str) -> bool {
    let mut node = &self.root;
    for ch in prefix.chars() {
        if !node.children.contains_key(&ch) {
            return false;
        }
        node = node.children.get(&ch).unwrap();
    }
    true
}

What is the main issue with this code snippet?

medium

A. Cannot assign &TrieNode to node because of lifetime mismatch

B. Missing mutable keyword for node variable

C. Using unwrap() without checking Option

D. Incorrect return type for starts_with function

Solution

1. Step 1: Analyze function purpose

   This implements prefix existence check (returns bool).

2. Step 2: Identify mismatch for prefix search

   Prefix search requires returning all words with the prefix (e.g. Vec<String>), not just bool.

3. Final Answer:

   Incorrect return type for starts_with function -> Option D

4. Quick Check:

   Prefix search needs Vec<String> not bool [OK]

Hint: Verify return type matches prefix search requirements [OK]

Common Mistakes:

• Confusing prefix existence (bool) with full prefix search (list)
• Assuming unwrap() causes runtime error here
• Forgetting Rust borrow checker rules

5. You want to extend a Trie in Rust to support prefix search that returns all words starting with a prefix, but also limit results to a maximum of 2 words. Which approach is best?

hard

A. Use a HashSet to store all words and filter after search

B. Store only 2 words per node during insertion

C. Modify DFS traversal to stop collecting words after 2 matches

D. Return only the first word found with the prefix

Solution

1. Step 1: Understand prefix search with limit

   We want to find all words starting with prefix but stop after 2 matches to save time.

2. Step 2: Modify DFS traversal

   During DFS from prefix node, keep count of collected words and stop recursion once 2 words are found.

3. Step 3: Evaluate other options

   Storing only 2 words per node loses data; filtering after search is inefficient; returning one word is incomplete.

4. Final Answer:

   Modify DFS traversal to stop collecting words after 2 matches -> Option C

5. Quick Check:

   Limit results by stopping DFS early [OK]

Hint: Stop DFS early to limit prefix search results [OK]

Common Mistakes:

• Limiting stored words per node loses data
• Filtering after full search wastes time
• Returning only one word ignores requirement