Trie Insert Operation in DSA Rust - Build from Scratch

Trie Insert Operation

📖 Scenario: Imagine you are building a simple search feature that suggests words as you type. To do this efficiently, you use a Trie, a tree-like data structure that stores words letter by letter.

🎯 Goal: You will create a Trie and write code to insert words into it. This helps you understand how words are stored step-by-step in the Trie.

📋 What You'll Learn

Create a TrieNode struct with a children map and an end-of-word flag

Create a Trie struct with a root node

Write an insert method to add words letter by letter

Print the Trie structure after inserting words

💡 Why This Matters

🌍 Real World

Tries are used in search engines, autocomplete features, and spell checkers to quickly find words or prefixes.

💼 Career

Understanding Tries helps in roles involving text processing, search optimization, and building efficient data retrieval systems.

1

Create the TrieNode struct

Create a struct called TrieNode with two fields: children which is a HashMap<char, TrieNode> and is_end_of_word which is a bool. Also implement a new function that returns an empty TrieNode with is_end_of_word set to false.

DSA Rust

// Your code here

Hint

Use HashMap<char, TrieNode> for children and set is_end_of_word to false in new.

2

Create the Trie struct with root node

Create a struct called Trie with one field root of type TrieNode. Implement a new function for Trie that initializes root with a new TrieNode.

DSA Rust

use std::collections::HashMap;

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

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

// Your code here

Hint

Define Trie with a root field and initialize it with TrieNode::new().

3

Implement the insert method for Trie

Inside the impl Trie block, write a method called insert that takes &mut self and a word: &str. For each character in word.chars(), check if it exists in the current node's children. If not, insert a new TrieNode. Move to the child node for the character. After all characters, set is_end_of_word to true for the last node.

DSA Rust

use std::collections::HashMap;

struct TrieNode {
    children: HashMap,
    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(),
        }
    }
}

// Add the insert method below
// Your code here

Hint

Use entry(ch).or_insert_with(TrieNode::new) to add missing children nodes.

4

Insert words and print Trie structure

Create a main function. Inside it, create a mutable Trie called trie. Insert the words "cat", "car", and "dog" into trie using the insert method. Then print the root node's children keys as a vector to show the first letters stored in the Trie.

DSA Rust

use std::collections::HashMap;

struct TrieNode {
    children: HashMap,
    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() {
            current = current.children.entry(ch).or_insert_with(TrieNode::new);
        }
        current.is_end_of_word = true;
    }
}

fn main() {
    // Your code here
}

Hint

Print the keys of trie.root.children as a vector to see the first letters stored.

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