Trie Insert Operation in DSA Rust

Mental Model

A trie stores words by branching letters step-by-step, making it easy to find or add words by following or creating letter paths.

Analogy: Imagine a tree where each branch is a letter. To add a word, you walk down the branches matching letters. If a letter branch is missing, you grow a new branch there.

root
 ↓
[ ]
Each node holds links to next letters, starting empty at root.

Dry Run Walkthrough

Input: Insert the word "cat" into an empty trie

Goal: Add the word "cat" so each letter is a node linked in order, marking the end of the word

Step 1: Start at root node, check for 'c' child; none found, create 'c' node

root -> c
[c node created]

Why: We need to add the first letter 'c' as a new branch

Step 2: Move to 'c' node, check for 'a' child; none found, create 'a' node

root -> c -> a
[a node created]

Why: Add second letter 'a' as a branch from 'c'

Step 3: Move to 'a' node, check for 't' child; none found, create 't' node

root -> c -> a -> t
[t node created]

Why: Add third letter 't' as a branch from 'a'

Step 4: Mark 't' node as end of word

root -> c -> a -> t* (end)
[word complete]

Why: Marking end shows word "cat" is stored here

Result:

root -> c -> a -> t* (end)
Word "cat" inserted

Annotated Code

DSA Rust

use std::collections::HashMap;

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

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

struct Trie {
    root: TrieNode,
}

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

    fn insert(&mut self, word: &str) {
        let mut current = &mut self.root;
        for ch in word.chars() {
            // If child node for ch doesn't exist, create it
            current = current.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new()));
        }
        // Mark last node as end of word
        current.is_end_of_word = true;
    }

    fn print_trie(&self) {
        fn dfs(node: &TrieNode, prefix: String) {
            if node.is_end_of_word {
                println!("{}*", prefix);
            }
            for (ch, child) in &node.children {
                dfs(child, format!("{}{}", prefix, ch));
            }
        }
        dfs(&self.root, String::new());
    }
}

fn main() {
    let mut trie = Trie::new();
    trie.insert("cat");
    trie.print_trie();
}

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

Advance current to child node for letter ch, creating new node if missing

current.is_end_of_word = true;

Mark current node as end of a stored word

Output

cat*

Complexity Analysis

Time: O(m) because we process each of the m letters in the word once during insertion

Space: O(m) because in the worst case we add a new node for each letter in the word

vs Alternative: Compared to storing words in a list, trie insertion is faster for prefix searches but uses more space for nodes

Edge Cases

Inserting an empty string

Marks root as end of word, representing empty word stored

DSA Rust

current.is_end_of_word = true;

Inserting a word that is prefix of existing word (e.g., insert "ca" after "cat")

Reuses existing nodes for 'c' and 'a', marks 'a' node as end of word

DSA Rust

current.is_end_of_word = true;

Inserting duplicate word

Traverses existing nodes, marks end node again without creating new nodes

DSA Rust

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

When to Use This Pattern

When you need to store many words and quickly find if a prefix or whole word exists, use a trie insert pattern to build the letter-by-letter tree.

Common Mistakes

Mistake: Not creating a new node when a letter path is missing
Fix: Use entry().or_insert_with() to create missing child nodes during traversal

Mistake: Forgetting to mark the last node as end of word
Fix: Set is_end_of_word = true after inserting all letters

Summary

Inserts a word into a trie by creating nodes for letters and marking the end node.

Use when you want fast prefix-based word storage and lookup.

The key is to follow existing letter paths or create new nodes, then mark the word's end.

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