Autocomplete System with Trie in DSA Rust

Mental Model

A trie stores words by sharing common prefixes, letting us quickly find all words starting with a given prefix.

Analogy: Imagine a tree where each branch is a letter, and walking down branches spells out words. To autocomplete, you just follow the prefix branches and list all words below.

root
 ├─ c
 │   ├─ a
 │   │   ├─ t (end)
 │   │   └─ r (end)
 │   └─ o
 │       └─ w (end)
 └─ d
     └─ o
         └─ g (end)

Dry Run Walkthrough

Input: Insert words: "cat", "car", "cow", "dog"; autocomplete prefix: "ca"

Goal: Find all words starting with prefix "ca" using the trie

Step 1: Insert "cat" letter by letter into trie

root -> c -> a -> t[end]

Why: Build path for first word so trie nodes represent letters

Step 2: Insert "car" sharing prefix 'ca', add 'r' node

root -> c -> a -> t[end], r[end]

Why: Reuse existing prefix nodes to save space

Step 3: Insert "cow" branching from 'c' with 'o' and 'w'

root -> c -> a -> t[end], r[end]; c -> o -> w[end]

Why: Add new branch for different word starting with 'c'

Step 4: Insert "dog" starting new branch from root 'd'

root -> c -> a -> t[end], r[end]; c -> o -> w[end]; d -> o -> g[end]

Why: Add new branch for word starting with different letter

Step 5: Autocomplete prefix "ca": follow 'c' then 'a'

At node 'a' with children 't[end]' and 'r[end]'

Why: Find node representing prefix to list all words below

Step 6: Collect words from 'a' node: "cat", "car"

Words found: ["cat", "car"]

Why: Gather all complete words starting with prefix

Result:

root -> c -> a -> t[end], r[end]; c -> o -> w[end]; d -> o -> g[end]
Autocomplete results for "ca": ["cat", "car"]

Annotated Code

DSA Rust

use std::collections::HashMap;

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

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

struct Trie {
    root: TrieNode,
}

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

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

    fn autocomplete(&self, prefix: &str) -> Vec<String> {
        let mut node = &self.root;
        for ch in prefix.chars() {
            if let Some(next_node) = node.children.get(&ch) {
                node = next_node; // follow prefix path
            } else {
                return vec![]; // prefix not found
            }
        }
        let mut results = Vec::new();
        Self::dfs(node, prefix.to_string(), &mut results); // collect words
        results
    }

    fn dfs(node: &TrieNode, path: String, results: &mut Vec<String>) {
        if node.is_end {
            results.push(path.clone()); // found complete word
        }
        for (ch, child) in &node.children {
            let mut new_path = path.clone();
            new_path.push(*ch); // add next letter
            Self::dfs(child, new_path, results); // recurse
        }
    }
}

fn main() {
    let mut trie = Trie::new();
    let words = ["cat", "car", "cow", "dog"];
    for &word in &words {
        trie.insert(word);
    }
    let prefix = "ca";
    let completions = trie.autocomplete(prefix);
    println!("Autocomplete results for \"{}\": {:?}", prefix, completions);
}

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

advance or create child node for current letter

node.is_end = true;

mark current node as end of a word

if let Some(next_node) = node.children.get(&ch) { node = next_node; } else { return vec![]; }

follow prefix path or return empty if prefix missing

Self::dfs(node, prefix.to_string(), &mut results);

start depth-first search to collect all words below prefix node

if node.is_end { results.push(path.clone()); }

add word to results when end of word reached

for (ch, child) in &node.children { ... Self::dfs(child, new_path, results); }

recurse on all children to find all completions

Output

Autocomplete results for "ca": ["cat", "car"]

Complexity Analysis

Time: O(m + n) where m is length of prefix and n is total letters in all words under prefix because we traverse prefix then collect all completions

Space: O(n) for storing trie nodes and recursion stack during DFS

vs Alternative: Compared to scanning all words for prefix match (O(k * w) where k is prefix length and w is number of words), trie is faster for large datasets by sharing prefixes

Edge Cases

Empty prefix

Returns all words stored in trie

DSA Rust

if let Some(next_node) = node.children.get(&ch) { ... } else { return vec![]; }

Prefix not in trie

Returns empty list immediately

DSA Rust

if let Some(next_node) = node.children.get(&ch) { ... } else { return vec![]; }

Insert empty string

Marks root as end of word, autocomplete with empty prefix returns the empty string as a word

DSA Rust

node.is_end = true;

When to Use This Pattern

When asked to quickly find all words starting with a prefix, use a trie to share prefix nodes and efficiently list completions.

Common Mistakes

Mistake: Not marking the end of word node, causing autocomplete to miss valid words
Fix: Set is_end = true at the last node of inserted word

Mistake: Not handling prefix not found case, leading to panic or wrong results
Fix: Return empty list immediately if prefix path missing in trie

Summary

Stores words in a tree structure sharing prefixes to enable fast autocomplete.

Use when you need to find all words starting with a given prefix efficiently.

The key insight is that common prefixes are stored once, so searching prefixes is fast.

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