Trie Insert Operation in DSA Rust - Execution Trace

Concept Flow - Trie Insert Operation

Start at root node

↓

For each character in word

↓

Check if child node exists

↓

Move to child

↓

Mark end of word at last node

↓

Done

Insert each character by moving through existing nodes or creating new ones, then mark the last node as word end.

Execution Sample

DSA Rust

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

Inserts a word into the trie by traversing or creating nodes for each character and marking the last node as end.

Execution Table

Step	Operation	Character	Nodes in Trie	Pointer Changes	Visual State
1	Start insertion	-	root	current -> root	root (is_end: false, children: {})
2	Process character 'c'	c	root -> c	current moves to root.children['c'] (created new node)	root -> c (is_end: false, children: {})
3	Process character 'a'	a	root -> c -> a	current moves to c.children['a'] (created new node)	root -> c -> a (is_end: false, children: {})
4	Process character 't'	t	root -> c -> a -> t	current moves to a.children['t'] (created new node)	root -> c -> a -> t (is_end: false, children: {})
5	Mark end of word	-	root -> c -> a -> t	current.is_end = true	root -> c -> a -> t (is_end: true, children: {})
6	Insertion complete	-	root -> c -> a -> t	no pointer change	root -> c -> a -> t (is_end: true, children: {})

💡 All characters processed and last node marked as end of word.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	node for 'c'	node for 'a'	node for 't'	node for 't'	node for 't'
nodes_in_trie	root	root -> c	root -> c -> a	root -> c -> a -> t	root -> c -> a -> t	root -> c -> a -> t
current.is_end	false	false	false	false	true	true

Key Moments - 3 Insights

Why do we create a new node only if the child does not exist?

Because if the child node for a character already exists, we just move the pointer there to reuse the path. Creating new nodes only when needed avoids duplicates and saves space. See execution_table rows 2-4.

Why do we mark is_end = true only after processing all characters?

Marking is_end true at the last node indicates the end of a valid word. This helps distinguish between prefixes and complete words. Refer to execution_table row 5.

What happens if we insert a word that is a prefix of an existing word?

We traverse existing nodes without creating new ones and mark the last node's is_end true to indicate the shorter word also exists. This is shown by reusing nodes in steps 2-4.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which node does 'current' point to?

A Node for character 'c'

B Node for character 'a'

C Root node

D Node for character 't'

💡 Hint

Check the 'Pointer Changes' column at step 3 in execution_table.

At which step does the last node get marked as end of word?

A Step 5

B Step 4

C Step 6

D Step 2

💡 Hint

Look for 'Mark end of word' operation in execution_table.

If the word inserted was 'car' instead of 'cat', what would change in the execution_table?

A Step 5 would mark node 'a' as end

B Step 2 would create a node for 'r'

C Step 4 would create a node for 'r' instead of 't'

D No changes at all

💡 Hint

Compare the character processed at step 4 in execution_table.

Concept Snapshot

Trie Insert Operation:
- Start at root node
- For each character:
  - Move to child if exists
  - Else create new child node
- Mark last node as end of word
- Efficient prefix storage

Full Transcript

The Trie Insert Operation starts at the root node. For each character in the word, it checks if a child node exists. If yes, it moves the current pointer to that child. If not, it creates a new node and moves there. After processing all characters, it marks the last node as the end of a word. This process efficiently stores words sharing prefixes by reusing nodes. The execution table shows each step, pointer changes, and the trie structure growing. Key moments clarify why nodes are created only when missing and why marking the end is important. The visual quiz tests understanding of pointer movements and node creation.

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