Trie Node Design and Initialization in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Node Initialization in Rust

What is the output of the following Rust code that initializes a Trie node and prints its children count?

DSA Rust

use std::collections::HashMap;

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

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

fn main() {
    let root = TrieNode::new();
    println!("{}", root.children.len());
}

A Compilation error

B 1

C Runtime panic

D 0

💡 Hint

Think about what the children HashMap contains right after initialization.

The TrieNode is initialized with an empty HashMap for children, so its length is 0.

❓ Predict Output

intermediate

Result of Adding a Child Node to Trie

What will be the output after adding a child node for character 'a' to the root Trie node and printing the children count?

DSA Rust

use std::collections::HashMap;

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

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

    fn add_child(&mut self, ch: char) {
        self.children.insert(ch, TrieNode::new());
    }
}

fn main() {
    let mut root = TrieNode::new();
    root.add_child('a');
    println!("{}", root.children.len());
}

A 1

B 0

C Compilation error

D Runtime panic

💡 Hint

Adding a child inserts one entry into the children HashMap.

After adding a child node for 'a', the children HashMap contains one entry, so length is 1.

🧠 Conceptual

advanced

Understanding Ownership in Trie Node Children

In Rust, why is it important that the children of a TrieNode are stored as HashMap instead of HashMap?

A Because TrieNode cannot be cloned if stored as references.

B Because storing references is more memory efficient and preferred in Rust.

C Because storing references would require managing lifetimes and could cause dangling references.

D Because HashMap cannot store references as keys.

💡 Hint

Think about Rust's ownership and borrowing rules.

Storing owned TrieNodes avoids lifetime issues and dangling references, which are complex to manage with references.

🔧 Debug

advanced

Identify the Error in TrieNode Initialization

What error will this Rust code produce when compiling?

DSA Rust

use std::collections::HashMap;

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

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

fn main() {
    let root = TrieNode::new();
}

A Type error: children field type mismatch

B Syntax error: missing parentheses after HashMap::new

C Runtime panic: uninitialized children

D No error, compiles successfully

💡 Hint

Check how functions are called in Rust.

HashMap::new is a function and must be called with parentheses (). Missing them causes a syntax error.

🚀 Application

expert

Predict the Trie Structure After Insertions

Given the following insertions into an initially empty Trie, what is the printed output of the root's children keys in sorted order?

DSA Rust

use std::collections::HashMap;

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

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

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

fn main() {
    let mut root = TrieNode::new();
    root.insert("cat");
    root.insert("car");
    root.insert("dog");
    let mut keys: Vec<char> = root.children.keys().cloned().collect();
    keys.sort();
    for k in keys {
        print!("{} ", k);
    }
}

A c d

B a c d

C c a d

D d c a

💡 Hint

Only the first letters of inserted words appear as root children keys.

The root children keys are the first letters of inserted words: 'c' from "cat" and "car", and 'd' from "dog".

Practice

1. What is the main purpose of a Trie node in a Trie data structure?

easy

A. To store characters and links to child nodes representing prefixes

B. To store integer values for sorting

C. To hold a single string only

D. To act as a queue for BFS traversal

Solution

1. Step 1: Understand Trie node role

   A Trie node stores a character and links to child nodes representing possible next characters in words.

2. Step 2: Compare options

   Only To store characters and links to child nodes representing prefixes correctly describes this role; others describe unrelated data structures or uses.

3. Final Answer:

   To store characters and links to child nodes representing prefixes -> Option A

4. Quick Check:

   Trie node = character + children links [OK]

Hint: Trie nodes hold characters and children links [OK]

Common Mistakes:

• Thinking Trie nodes store whole words
• Confusing Trie nodes with arrays or queues
• Assuming Trie nodes store integer values

2. Which Rust syntax correctly declares a Trie node struct with a children array of size 26 and a boolean flag for word end?

easy

A. struct TrieNode { children: [Option; 26], is_end: bool }

B. struct TrieNode { children: Vec<TrieNode>, is_end: bool }

C. struct TrieNode { children: [TrieNode; 26], is_end: bool }

D. struct TrieNode { children: Option, is_end: bool }

Solution

1. Step 1: Understand Rust struct for Trie node

   Each child is an optional boxed TrieNode to allow recursive structure with fixed size array of 26 for letters.

2. Step 2: Analyze options

   struct TrieNode { children: [Option; 26], is_end: bool } uses [Option; 26] which is correct. struct TrieNode { children: Vec<TrieNode>, is_end: bool } uses Vec which is dynamic, not fixed size. struct TrieNode { children: [TrieNode; 26], is_end: bool } uses [TrieNode; 26] which causes infinite size error. struct TrieNode { children: Option, is_end: bool } has only one Option not an array.

3. Final Answer:

   struct TrieNode { children: [Option; 26], is_end: bool } -> Option A

4. Quick Check:

   Use Option array for children [OK]

Hint: Use Option array for recursive children [OK]

Common Mistakes:

• Using Vec instead of fixed-size array
• Using direct TrieNode array causing infinite size
• Not wrapping children in Option<Box>

3. Given this Rust code snippet for TrieNode initialization, what will be the output of printing the is_end flag of the root node?

struct TrieNode {
    children: [Option; 26],
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        Self {
            children: Default::default(),
            is_end: false,
        }
    }
}

fn main() {
    let root = TrieNode::new();
    println!("{}", root.is_end);
}

medium

A. Runtime panic

B. true

C. Compilation error

D. false

Solution

1. Step 1: Analyze TrieNode::new() initialization

   The new() function sets is_end to false explicitly and children to default (None for each child).

2. Step 2: Check main output

   Printing root.is_end will print false as initialized.

3. Final Answer:

   false -> Option D

4. Quick Check:

   is_end initialized false = false [OK]

Hint: Default is_end is false unless set true [OK]

Common Mistakes:

• Assuming is_end defaults to true
• Expecting compilation error due to Default::default()
• Thinking children initialization affects is_end

4. Identify the error in this Rust TrieNode initialization code:

struct TrieNode {
    children: [Option; 26],
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        Self {
            children: [None; 26],
            is_end: false,
        }
    }
}

medium

A. is_end should be true by default

B. Cannot initialize array of Option with [None; 26]

C. Missing lifetime annotations for Box

D. Struct fields are private and inaccessible

Solution

1. Step 1: Understand array initialization in Rust

   Arrays of non-Copy types cannot be initialized with [value; size] unless value implements Copy.

2. Step 2: Check Option Copy trait

   Option does not implement Copy, so [None; 26] causes compilation error.

3. Final Answer:

   Cannot initialize array of Option with [None; 26] -> Option B

4. Quick Check:

   Non-Copy array init with [None; 26] fails [OK]

Hint: Use Default::default() for arrays of non-Copy types [OK]

Common Mistakes:

• Assuming [None; 26] works for Option<Box>
• Confusing lifetime errors with initialization errors
• Thinking is_end default must be true

5. You want to design a TrieNode in Rust that supports Unicode characters beyond just 'a' to 'z'. Which design change is best to handle this efficiently?

hard

A. Store children as a linked list of TrieNodes

B. Increase array size to 256 to cover all ASCII characters

C. Replace fixed-size array with a HashMap for children

D. Use Vec> with 26 elements

Solution

1. Step 1: Understand Unicode character range

   Unicode has many characters beyond ASCII; fixed arrays for 26 or 256 are inefficient or insufficient.

2. Step 2: Evaluate data structure options

   HashMap allows dynamic keys for any Unicode char efficiently. Increasing array size wastes memory. Vec with 26 elements limits to 26 chars. Linked list is inefficient for lookups.

3. Final Answer:

   Replace fixed-size array with a HashMap for children -> Option C

4. Quick Check:

   Use HashMap for Unicode children [OK]

Hint: Use HashMap for flexible Unicode children [OK]

Common Mistakes:

• Assuming fixed arrays can cover Unicode
• Using Vec with fixed size for Unicode
• Choosing linked list causing slow lookups