Trie Insert Operation in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting words into a Trie

What is the printed structure of the Trie after inserting the words "cat", "car", and "dog" in order?

DSA Rust

use std::collections::BTreeMap;

#[derive(Debug)]
struct TrieNode {
    children: BTreeMap<char, TrieNode>,
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: BTreeMap::new(),
            is_end_of_word: false,
        }
    }

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

    fn print(&self, prefix: String) {
        if self.is_end_of_word {
            println!("{} (end)", prefix);
        }
        for (ch, node) in &self.children {
            node.print(format!("{}{}", prefix, ch));
        }
    }
}

fn main() {
    let mut root = TrieNode::new();
    root.insert("cat");
    root.insert("car");
    root.insert("dog");
    root.print(String::new());
}

A

cat (end)
car (end)
dog (end)

B

car (end)
cat (end)
dog (end)

C

dog (end)
car (end)
cat (end)

D

car (end)
dog (end)
cat (end)

💡 Hint

Think about how the print function recursively prints words in alphabetical order based on children keys.

The print function prints words in alphabetical order because BTreeMap keys are iterated in sorted order. The inserted words are "cat", "car", and "dog". The print order is car, cat, then dog.

❓ Predict Output

intermediate

Trie structure after inserting overlapping prefixes

After inserting the words "bat", "bath", and "batman" into an empty Trie, what is the output of printing all words stored in the Trie?

DSA Rust

use std::collections::BTreeMap;

#[derive(Debug)]
struct TrieNode {
    children: BTreeMap<char, TrieNode>,
    is_end_of_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: BTreeMap::new(),
            is_end_of_word: false,
        }
    }

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

    fn print(&self, prefix: String) {
        if self.is_end_of_word {
            println!("{} (end)", prefix);
        }
        for (ch, node) in &self.children {
            node.print(format!("{}{}", prefix, ch));
        }
    }
}

fn main() {
    let mut root = TrieNode::new();
    root.insert("bat");
    root.insert("bath");
    root.insert("batman");
    root.print(String::new());
}

A

bat (end)
batman (end)
bath (end)

B

batman (end)
bath (end)
bat (end)

C

bat (end)
bath (end)
batman (end)

D

bath (end)
bat (end)
batman (end)

💡 Hint

The print order follows the alphabetical order of children keys at each node.

The words share the prefix "bat". The print function prints words in alphabetical order: "bat", "bath", then "batman".

🔧 Debug

advanced

Identify the error in Trie insert method

What error will occur when running this Trie insert method code snippet?

DSA Rust

fn insert(&mut self, word: &str) {
    let mut current = self;
    for ch in word.chars() {
        current = current.children.get_mut(&ch).unwrap();
    }
    current.is_end_of_word = true;
}

A Runtime panic: unwrap on None when character not found

B Logical error: words not inserted correctly but no panic

C Compilation error: cannot borrow immutable reference as mutable

D No error, code runs correctly

💡 Hint

Check what happens if the character is not already in children map.

The method uses get_mut(&ch).unwrap(). If the character is not found, get_mut returns None, so unwrap() panics. This leads to a runtime panic when trying to insert a word with unseen characters.

🧠 Conceptual

advanced

Why use HashMap in Trie nodes?

Why is a HashMap<char, TrieNode> commonly used to store children in a Trie node instead of a fixed-size array?

A Fixed-size arrays cannot store characters as keys

B Fixed-size arrays are slower to access than HashMaps in Rust

C HashMap automatically sorts children keys alphabetically for printing

D HashMap allows dynamic and sparse storage of children, saving memory when alphabet is large

💡 Hint

Think about memory usage and alphabet size.

Using a HashMap allows storing only existing children nodes, which saves memory when the alphabet is large and many nodes have few children. Fixed-size arrays allocate space for all possible characters, wasting memory.

🚀 Application

expert

Count words with given prefix in Trie

Given a Trie with inserted words, which code snippet correctly counts how many words start with a given prefix prefix?

DSA Rust

fn count_words_with_prefix(node: &TrieNode, prefix: &str) -> usize {
    let mut current = node;
    for ch in prefix.chars() {
        match current.children.get(&ch) {
            Some(next_node) => current = next_node,
            None => return 0,
        }
    }
    fn count_all_words(node: &TrieNode) -> usize {
        let mut count = if node.is_end_of_word { 1 } else { 0 };
        for child in node.children.values() {
            count += count_all_words(child);
        }
        count
    }
    count_all_words(current)
}

A Returns total words starting with prefix by traversing from prefix node recursively

B Returns number of children nodes under prefix node, not counting end of words

C Returns 1 if prefix exists, else 0, ignoring all words under prefix

D Returns total words in Trie regardless of prefix

💡 Hint

Look at how the code traverses to prefix node and counts words recursively.

The code first moves to the node representing the prefix. If prefix not found, returns 0. Then it counts all words under that node recursively, including the prefix node if it is an end of a word.

Practice

1. What is the main purpose of the insert operation in a Trie data structure?

easy

A. To search for a word in the Trie

B. To delete a word from the Trie

C. To add a new word by creating nodes for each character

D. To count the number of words stored in the Trie

Solution

1. Step 1: Understand the insert operation

   The insert operation adds a new word by creating nodes for each character if they don't exist.

2. Step 2: Compare with other operations

   Deleting removes words, searching finds words, counting totals words. Insert specifically adds words.

3. Final Answer:

   To add a new word by creating nodes for each character -> Option C

4. Quick Check:

   Insert = Add word nodes [OK]

Hint: Insert means adding characters as nodes step-by-step [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert counts words
• Assuming insert modifies existing words

2. Which of the following is the correct Rust syntax to insert a word into a Trie using a method named insert?

easy

A. trie->insert("word");

B. trie.insert("word");

C. insert.trie("word");

D. trie.insert[word];

Solution

1. Step 1: Recall Rust method call syntax

   In Rust, methods are called with dot notation and parentheses for arguments, like object.method(args).

2. Step 2: Check each option

   trie.insert("word"); uses correct dot and parentheses syntax. trie.insert[word]; uses brackets incorrectly. insert.trie("word"); reverses object and method. trie->insert("word"); uses arrow syntax not used in Rust.

3. Final Answer:

   trie.insert("word"); -> Option B

4. Quick Check:

   Rust method call = dot + parentheses [OK]

Hint: Use dot and parentheses for method calls in Rust [OK]

Common Mistakes:

• Using brackets instead of parentheses
• Reversing method and object order
• Using arrow syntax like C++

3. Given the following Rust code snippet for inserting words into a Trie, what will be the printed output after inserting "cat" and "car"?

let mut trie = Trie::new();
trie.insert("cat");
trie.insert("car");
println!("{}", trie.search("car"));
println!("{}", trie.search("cap"));

medium

A. true\nfalse

B. false\nfalse

C. true\ntrue

D. false\ntrue

Solution

1. Step 1: Insert words "cat" and "car" into the Trie

   Both words share prefix "ca" but differ at last character. Both get inserted fully.

2. Step 2: Search for "car" and "cap"

   "car" was inserted, so search returns true. "cap" was not inserted, so search returns false.

3. Final Answer:

   true\nfalse -> Option A

4. Quick Check:

   Inserted word found = true, missing word = false [OK]

Hint: Inserted words return true on search, others false [OK]

Common Mistakes:

• Assuming partial prefix means word exists
• Confusing search return values
• Thinking insert overwrites words

4. Identify the error in this Rust code snippet that tries to insert a word into a Trie:

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

impl TrieNode {
    fn insert(&mut self, word: &str) {
        let mut node = self;
        for ch in word.chars() {
            if !node.children.contains_key(&ch) {
                node.children.insert(ch, TrieNode { children: HashMap::new(), is_end: false });
            }
            node = node.children.get_mut(&ch).unwrap();
        }
        node.is_end = true;
    }
}

medium

A. Using get_mut() instead of get() causes error

B. Missing lifetime annotations on &str parameter

C. is_end should be set before the loop

D. HashMap cannot store TrieNode directly due to recursive type size

Solution

1. Step 1: Understand recursive struct size problem

   HashMap inside TrieNode causes infinite size because TrieNode contains itself directly.

2. Step 2: Correct approach using Box or Rc

   To fix, children should store Box<TrieNode> or Rc<TrieNode> to have a pointer and known size.

3. Final Answer:

   HashMap cannot store TrieNode directly due to recursive type size -> Option D

4. Quick Check:

   Recursive struct needs indirection like Box [OK]

Hint: Recursive structs need Box or pointer types in Rust [OK]

Common Mistakes:

• Ignoring recursive type size error
• Thinking get_mut() causes error
• Misplacing is_end assignment

5. You want to insert multiple words into a Trie and then find all words starting with a given prefix. Which modification to the Trie insert operation helps support efficient prefix search in Rust?

hard

A. Store a count of words passing through each node during insert

B. Only mark is_end at the root node during insert

C. Insert words in reverse order to optimize prefix search

D. Use a vector instead of HashMap for children to speed up insert

Solution

1. Step 1: Understand prefix search requirement

   To find all words with a prefix, the Trie must quickly identify nodes representing that prefix.

2. Step 2: Use counts to optimize prefix queries

   Storing counts of words passing through nodes during insert helps quickly know how many words share that prefix.

3. Final Answer:

   Store a count of words passing through each node during insert -> Option A

4. Quick Check:

   Prefix search needs counts at nodes [OK]

Hint: Count words at nodes to speed prefix queries [OK]

Common Mistakes:

• Marking is_end only at root loses word ends
• Inserting words reversed breaks normal prefix logic
• Using vector loses fast char lookup