Trie Insert Operation in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths from root to nodes represent prefixes of words.

beginner

What does the insert operation do in a Trie?

The insert operation adds a word to the Trie by creating nodes for each character if they don't exist and marking the last node as the end of a word.

intermediate

In Rust, what is a common way to represent children nodes in a Trie?

Children nodes are often represented using a fixed-size array or a hash map where each entry corresponds to a character and points to the next Trie node.

beginner

Why do we mark the end of a word in a Trie node?

Marking the end of a word helps distinguish between a prefix and a complete word stored in the Trie, allowing accurate word searches.

intermediate

What is the time complexity of inserting a word of length n into a Trie?

The time complexity is O(n), where n is the length of the word, because we process each character once during insertion.

What does each node in a Trie typically represent?

A A whole word

B A character

C A number

D A sentence

Each node in a Trie represents a single character of a word.

What do we do if a character node does not exist during insertion?

A Skip it

B Replace the root node

C Delete the Trie

D Create a new node for that character

We create a new node for the character if it does not exist to continue building the word path.

How do we mark that a node represents the end of a word?

A By adding a number

B By deleting the node

C By setting a boolean flag

D By changing the root

We set a boolean flag in the node to indicate it is the end of a word.

What is the main advantage of using a Trie for word storage?

A Fast prefix search

B Uses less memory than arrays

C Stores numbers efficiently

D Sorts words automatically

Tries allow fast prefix-based searches because of their tree structure.

What is the time complexity of inserting a word of length n into a Trie?

A O(n)

B O(1)

C O(n^2)

D O(log n)

Insertion takes O(n) time because each character is processed once.

Explain how the insert operation works in a Trie step-by-step.

Think about how you add letters one by one and mark the end.

Why is marking the end of a word important in a Trie?

Consider the difference between 'cat' and 'caterpillar'.

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