Trie Insert Operation in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a character node into the children map.

DSA Rust

node.children.[1];

Drag options to blanks, or click blank then click option'

Ainsert(ch, TrieNode::new())

Binsert(ch, TrieNode::default())

Cpush(ch, TrieNode::new())

Dadd(ch, TrieNode::new())

Attempts:

3 left

💡 Hint

Common Mistakes

Using push or add which are not methods of HashMap.

Using TrieNode::default() if new() is defined for node creation.

The insert method adds a key-value pair to the children HashMap. Using TrieNode::new() creates a new node.

2fill in blank

medium

Complete the code to check if a character exists in the children map.

DSA Rust

if node.children.contains_key(&[1]) {

Drag options to blanks, or click blank then click option'

Ach

Bnode

Ckey

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using node or value instead of the character key.

Not passing a reference to the key.

We check if the children map has the character key ch using contains_key(&ch).

3fill in blank

hard

Fix the error in the code to mark the end of a word.

DSA Rust

node.is_end_of_word = [1];

Drag options to blanks, or click blank then click option'

Afalse

B0

CNone

Dtrue

Attempts:

3 left

💡 Hint

Common Mistakes

Setting the flag to false or zero which means not end of word.

Using None which is not a boolean.

To mark the end of a word, set is_end_of_word to true.

4fill in blank

hard

Fill both blanks to traverse or create a child node for each character.

DSA Rust

node = node.children.entry([1]).or_insert_with([2]);

Drag options to blanks, or click blank then click option'

Ach

BTrieNode::new

CTrieNode::default

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using insert instead of or_insert_with.

Using default instead of new if new is defined.

We use entry(ch) to get or create the child node, and or_insert_with(TrieNode::new) to insert a new node if missing.

5fill in blank

hard

Fill all three blanks to complete the insert function for the Trie.

DSA Rust

for [1] in word.chars() {
    node = node.children.entry([2]).or_insert_with([3]);
}
node.is_end_of_word = true;

Drag options to blanks, or click blank then click option'

Ach

Bc

CTrieNode::new

DTrieNode::default

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names inconsistently.

Using default instead of new for node creation.

We iterate over characters with c, use entry(c) to access children, and or_insert_with(TrieNode::new) to create nodes.

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