Autocomplete System with Trie in DSA Rust - Build from Scratch

Autocomplete System with Trie

📖 Scenario: Imagine you are building a simple autocomplete feature for a search box. When a user types some letters, the system suggests words that start with those letters. To do this efficiently, you will use a Trie data structure.

🎯 Goal: Build a Trie to store a list of words, then find and print all words that start with a given prefix.

📋 What You'll Learn

Create a TrieNode struct with children and end_of_word flag

Insert words into the Trie

Search for all words starting with a given prefix

Print the list of autocomplete suggestions

💡 Why This Matters

🌍 Real World

Autocomplete systems are used in search engines, text editors, and mobile keyboards to suggest words quickly as users type.

💼 Career

Understanding Tries and autocomplete logic is useful for software engineers working on search features, user interfaces, and performance optimization.

1

Create the TrieNode struct and initialize the root

Define a struct called TrieNode with a children field as a vector of 26 Option elements and a boolean end_of_word field. Then create a mutable variable root as a new TrieNode with all children set to None and end_of_word set to false.

DSA Rust

# Define the TrieNode struct and create root
# Your code here

Hint

Use a vector of 26 elements for children to represent letters 'a' to 'z'. Initialize all to None.

2

Add a function to insert words into the Trie

Add a method insert to TrieNode that takes &mut self and a word: &str. For each character in word, calculate its index (0 for 'a', 1 for 'b', etc.). If the child at that index is None, create a new TrieNode. Move to that child node. After the last character, set end_of_word to true. In main, insert the words "cat", "car", and "dog" into root.

DSA Rust

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

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

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

fn main() {
    let mut root = TrieNode::new();
    // Insert words here
    // Your code here
}

Hint

Use a mutable reference node to traverse the Trie while inserting characters.

3

Add a function to find all words starting with a prefix

Add a method collect_words to TrieNode that takes &self, a mutable prefix: String, and a mutable vector results: &mut Vec<String>. It recursively explores children, adding characters to prefix. When end_of_word is true, push prefix.clone() to results. Also add a method autocomplete to TrieNode that takes &self and a prefix: &str, finds the node matching the prefix, then calls collect_words to gather all words starting with that prefix. In main, call root.autocomplete("ca") and store the result in a variable suggestions.

DSA Rust

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

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

    fn insert(&mut self, word: &str) {
        let mut node = self;
        for ch in word.chars() {
            let index = (ch as u8 - b'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 collect_words and autocomplete methods here
    // Your code here
}

fn main() {
    let mut root = TrieNode::new();
    root.insert("cat");
    root.insert("car");
    root.insert("dog");
    // Call autocomplete here
    // Your code here
}

Hint

Use recursion in collect_words to explore all children. In autocomplete, first find the node matching the prefix, then collect words.

4

Print the autocomplete suggestions

Add a for loop in main to print each word in the suggestions vector on its own line.

DSA Rust

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

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

    fn insert(&mut self, word: &str) {
        let mut node = self;
        for ch in word.chars() {
            let index = (ch as u8 - b'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 collect_words(&self, prefix: &mut String, results: &mut Vec) {
        if self.end_of_word {
            results.push(prefix.clone());
        }
        for i in 0..26 {
            if let Some(child) = &self.children[i] {
                prefix.push((b'a' + i as u8) as char);
                child.collect_words(prefix, results);
                prefix.pop();
            }
        }
    }

    fn autocomplete(&self, prefix: &str) -> Vec {
        let mut node = self;
        for ch in prefix.chars() {
            let index = (ch as u8 - b'a') as usize;
            if let Some(child) = &node.children[index] {
                node = child;
            } else {
                return vec![];
            }
        }
        let mut results = Vec::new();
        let mut prefix_string = prefix.to_string();
        node.collect_words(&mut prefix_string, &mut results);
        results
    }
}

fn main() {
    let mut root = TrieNode::new();
    root.insert("cat");
    root.insert("car");
    root.insert("dog");
    let suggestions = root.autocomplete("ca");
    // Print suggestions here
    // Your code here
}

Hint

Use a for loop to print each suggestion on its own line.

Practice

1. What is the main purpose of using a Trie in an autocomplete system?

easy

A. To sort words alphabetically

B. To count the total number of words

C. To efficiently store and search prefixes of words

D. To reverse the input strings

Solution

1. Step 1: Understand the role of Trie in prefix search

   A Trie is a tree-like data structure designed to store strings by their prefixes, allowing quick prefix-based searches.

2. Step 2: Connect Trie usage to autocomplete

   Autocomplete requires finding all words starting with a given prefix efficiently, which a Trie supports well.

3. Final Answer:

   To efficiently store and search prefixes of words -> Option C

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie stores prefixes for fast autocomplete search [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie counts words only
• Assuming Trie reverses strings

2. Which of the following is the correct Rust syntax to define a Trie node struct with children as a HashMap and an is_end boolean?

easy

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

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

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

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

Solution

1. Step 1: Understand Rust ownership and recursive types

   Rust requires recursive types like TrieNode to use pointers such as Box to avoid infinite size errors.

2. Step 2: Check each option's children type

   struct TrieNode { children: HashMap, is_end: bool } uses HashMap, which is correct for recursive Trie nodes. struct TrieNode { children: HashMap, is_end: bool } lacks Box, causing compile error. struct TrieNode { children: Vec<char>, is_end: bool } uses Vec<char>, which is incorrect for children mapping. struct TrieNode { children: HashMap, is_end: bool } uses HashMap, which is incorrect because keys should be single chars.

3. Final Answer:

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

4. Quick Check:

   Recursive struct needs Box pointer [OK]

Hint: Use Box for recursive struct fields in Rust [OK]

Common Mistakes:

• Omitting Box causes compile errors
• Using Vec instead of HashMap for children
• Using String keys instead of char

3. Given the following Rust code snippet for inserting words into a Trie, what will be the output of searching for prefix "ca"?

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

medium

A. ["dog"]

B. ["cat", "car"]

C. ["cat"]

D. []

Solution

1. Step 1: Insert words into Trie

   The 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: Search prefix returns all words starting with it [OK]

Common Mistakes:

• Returning only one matching word
• Returning words without the prefix
• Returning empty list incorrectly

4. Identify the bug in this Rust Trie insertion method snippet:

fn insert(&mut self, word: &str) {
    let mut node = &self.root;
    for ch in word.chars() {
        node = node.children.entry(ch).or_insert(TrieNode::new());
    }
    node.is_end = true;
}

medium

A. word.chars() should be collected into a vector first

B. Use of entry() is incorrect for insertion

C. is_end should be set before the loop

D. node should be mutable reference (&mut) to modify children

Solution

1. Step 1: Analyze mutability of node reference

   node is assigned as immutable reference &self.root, but children need to be modified, so node must be mutable reference &mut.

2. Step 2: Understand why mutability is needed for entry()

   entry() modifies the HashMap, so node must be mutable to call entry() and insert new nodes.

3. Final Answer:

   node should be mutable reference (&mut) to modify children -> Option D

4. Quick Check:

   Mutable reference needed for insertion [OK]

Hint: Use &mut to modify Trie nodes during insertion [OK]

Common Mistakes:

• Using immutable reference for mutable operations
• Setting is_end too early
• Unnecessary collection of chars

5. You want to extend a Trie-based autocomplete system to return suggestions sorted by frequency of word usage. Which data structure modification is best to support this efficiently?

hard

A. Store a frequency count at each end node and use a max-heap during search

B. Store words in a vector and sort on every search

C. Use a linked list to store words in insertion order

D. Store frequency counts but ignore them during search

Solution

1. Step 1: Understand frequency storage in Trie nodes

   Storing frequency counts at end nodes tracks how often each word is used.

2. Step 2: Use max-heap to retrieve top frequent words efficiently

   During prefix search, a max-heap can quickly select highest frequency words without sorting all results.

3. Final Answer:

   Store a frequency count at each end node and use a max-heap during search -> Option A

4. Quick Check:

   Frequency + max-heap = efficient top suggestions [OK]

Hint: Use frequency counts + max-heap for fast top suggestions [OK]

Common Mistakes:

• Sorting all words on every search (slow)
• Ignoring frequency data
• Using linked list which is inefficient for sorting