Prefix Search Using Trie in DSA Rust - Build from Scratch

Prefix Search Using Trie

📖 Scenario: Imagine you are building a simple search feature for a phone contact list. When a user types the first few letters of a name, you want to quickly find all contacts that start with those letters.

🎯 Goal: Build a Trie data structure to store contact names and implement a prefix search to find all contacts starting with a given prefix.

📋 What You'll Learn

Create a TrieNode struct with children and end_of_word fields

Create a Trie struct with an insert method to add words

Create a search_prefix method to find all words starting with a prefix

Print the list of contacts matching the prefix

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words starting with a prefix.

💼 Career

Understanding Tries helps in roles involving search optimization, text processing, and building efficient data retrieval systems.

1

Create the TrieNode and Trie structs

Create a struct called TrieNode with a children field as a Vec>> of size 26 initialized to None, and a end_of_word field as bool set to false. Then create a struct called Trie with a root field of type TrieNode. Implement a new function for both structs to initialize them properly.

DSA Rust

// Your code here

Hint

Think of children as a list of 26 slots, one for each letter a-z. Each slot can hold another TrieNode or be empty.

2

Add the insert method to add words to the Trie

Add a method called insert to the Trie struct that takes a &self mutable reference and a word: &str. Use a variable node to traverse from self.root. For each character in word, calculate its index as c as usize - 'a' as usize. If the child at that index is None, create a new TrieNode and assign it. Move node to that child. After the loop, mark end_of_word as true for the last node.

DSA Rust

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

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

struct Trie {
    root: TrieNode,
}

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

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

fn main() {
    // Your code here
}

Hint

Remember to move the node pointer down the Trie as you add each letter.

3

Add a method to search for all words with a given prefix

Add a method called search_prefix to the Trie struct that takes &self and a prefix: &str. Traverse the Trie nodes for each character in prefix like in insert. If any child is None, return an empty Vec<String>. Otherwise, after reaching the node for the last prefix character, call a helper function collect_words that recursively collects all words starting from that node. Return the collected words with the prefix prepended.

DSA Rust

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

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

struct Trie {
    root: TrieNode,
}

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

    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for c in word.chars() {
            let index = (c as usize) - ('a' as usize);
            if node.children[index].is_none() {
                node.children[index] = Some(Box::new(TrieNode::new()));
            }
            node = node.children[index].as_mut().unwrap();
        }
        node.end_of_word = true;
    }

    // Add the search_prefix method below
    // Your code here
}

fn main() {
    // Your code here
}

Hint

Use recursion to explore all children nodes and build words starting from the prefix node.

4

Insert contacts and print search results for a prefix

In the main function, create a mutable Trie called contacts. Insert these exact contact names: "alice", "alex", "bob", "bobby", "carol". Then call contacts.search_prefix("bo") and print the returned vector of strings.

DSA Rust

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

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

struct Trie {
    root: TrieNode,
}

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

    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for c in word.chars() {
            let index = (c as usize) - ('a' as usize);
            if node.children[index].is_none() {
                node.children[index] = Some(Box::new(TrieNode::new()));
            }
            node = node.children[index].as_mut().unwrap();
        }
        node.end_of_word = true;
    }

    fn search_prefix(&self, prefix: &str) -> Vec {
        let mut node = &self.root;
        for c in prefix.chars() {
            let index = (c as usize) - ('a' as usize);
            if node.children[index].is_none() {
                return vec![];
            }
            node = node.children[index].as_ref().unwrap();
        }
        let mut results = Vec::new();
        self.collect_words(node, prefix.to_string(), &mut results);
        results
    }

    fn collect_words(&self, node: &TrieNode, prefix: String, results: &mut Vec) {
        if node.end_of_word {
            results.push(prefix.clone());
        }
        for i in 0..26 {
            if let Some(child) = &node.children[i] {
                let next_char = (b'a' + i as u8) as char;
                self.collect_words(child, format!("{}{}", prefix, next_char), results);
            }
        }
    }
}

fn main() {
    let mut contacts = Trie::new();
    // Insert contacts
    // Your code here
    // Search and print results
    // Your code here
}

Hint

Insert the exact contact names and print the vector returned by search_prefix.

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