BST Insert Operation in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new node with the given value.

DSA Rust

fn new_node(value: i32) -> Box<Node> {
    Box::new(Node {
        data: value,
        left: None,
        right: None,
        [1] })
}

Drag options to blanks, or click blank then click option'

Aparent: Some(value)

Bparent: Some(Box::new(Node::default()))

Cparent: None

Dparent: value

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning a value to parent instead of None

Using Some with incorrect value for parent

The new node should have no parent initially, so 'parent: None' is correct.

2fill in blank

medium

Complete the code to decide to insert the new value in the left subtree.

DSA Rust

if value [1] node.data {
    node.left = Some(insert(node.left.take(), value));
}

Drag options to blanks, or click blank then click option'

A>

B<

C==

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' for left subtree

Using '==' which is for equality check

If the value is less than the current node's data, it goes to the left subtree.

3fill in blank

hard

Fix the error in the recursive insert call to correctly handle the right subtree.

DSA Rust

if value > node.data {
    node.right = Some(insert([1], value));
}

Drag options to blanks, or click blank then click option'

Anode.right

Bnode.left

Cnode.left.take()

Dnode.right.take()

Attempts:

3 left

💡 Hint

Common Mistakes

Passing node.right directly without take()

Using left child instead of right child

We must take ownership of the right child using 'take()' before recursive insert.

4fill in blank

hard

Fill the blank to correctly insert a new node when the current node is None.

DSA Rust

if node.is_none() {
    return Some(Box::new(Node {
        data: value,
        left: None,
        right: None,
        [1]: None,
    }));
}

Drag options to blanks, or click blank then click option'

Aparent

Bleft

Cright

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using left or right instead of parent

Setting child field which does not exist

The parent field should be set to None when creating a new node.

5fill in blank

hard

Fill all three blanks to complete the insert function returning the updated node.

DSA Rust

fn insert(node: Option<Box<Node>>, value: i32) -> Option<Box<Node>> {
    match node {
        Some(mut node) => {
            if value [1] node.data {
                node.left = Some(insert(node.left.take(), value));
            } else if value [2] node.data {
                node.right = Some(insert(node.right.take(), value));
            }
            [3]
        }
        None => {
            Some(Box::new(Node {
                data: value,
                left: None,
                right: None,
                parent: None,
            }))
        }
    }
}

Drag options to blanks, or click blank then click option'

A<

B>

CSome(node)

Dreturn node

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators

Not wrapping the node in Some()

Use '<' and '>' to compare values and wrap the updated node in Some(node) at the end.

Practice

1. What is the main purpose of the insert operation in a Binary Search Tree (BST)?

easy

A. To add a new value while keeping the BST property intact

B. To delete a node from the BST

C. To find the maximum value in the BST

D. To balance the BST after insertion

Solution

1. Step 1: Understand BST property

   A BST keeps values in order: left child less, right child greater than parent.

2. Step 2: Purpose of insert

   Insert adds a new value so the tree remains ordered by BST rules.

3. Final Answer:

   To add a new value while keeping the BST property intact -> Option A

4. Quick Check:

   Insert = Add value maintaining order [OK]

Hint: Insert adds nodes keeping left < parent < right order [OK]

Common Mistakes:

• Confusing insert with delete operation
• Thinking insert balances the tree automatically
• Believing insert finds max value

2. Which of the following Rust function signatures correctly represents a BST insert method that takes ownership of the tree node and returns the updated tree?

easy

A. fn insert(val: i32) -> Box<Node>

B. fn insert(&mut self, val: i32) -> &mut Node

C. fn insert(self: Box<Node>, val: i32) -> Box<Node>

D. fn insert(&self, val: i32) -> Box<Node>

Solution

1. Step 1: Understand ownership in Rust BST insert

   Insert usually takes ownership of the node (Box<Node>) and returns updated Box<Node>.

2. Step 2: Match signature to ownership pattern

   fn insert(self: Box<Node>, val: i32) -> Box<Node> matches: takes self as Box<Node>, returns Box<Node>. Others mismatch ownership or mutability.

3. Final Answer:

   fn insert(self: Box<Node>, val: i32) -> Box<Node> -> Option C

4. Quick Check:

   Ownership insert = self Box<Node> in, Box<Node> out [OK]

Hint: Insert owns node (Box), returns updated Box [OK]

Common Mistakes:

• Using &self instead of self for ownership
• Returning reference instead of Box<Node>
• Missing self parameter

3. Given the following Rust code snippet for inserting values into a BST, what will be the in-order traversal output after inserting 10, 5, 15, 7?

medium

A. [10, 5, 7, 15]

B. [5, 7, 10, 15]

C. [15, 10, 7, 5]

D. [7, 5, 10, 15]

Solution

1. Step 1: Insert values in BST order

   Insert 10 as root, 5 left of 10, 15 right of 10, 7 right of 5.

2. Step 2: Perform in-order traversal

   In-order visits left, root, right: 5, 7, 10, 15.

3. Final Answer:

   [5, 7, 10, 15] -> Option B

4. Quick Check:

   In-order = sorted values [OK]

Hint: In-order traversal of BST = sorted inserted values [OK]

Common Mistakes:

• Confusing pre-order with in-order traversal
• Placing 7 as left child of 5 incorrectly
• Listing values in insertion order

4. Consider this Rust insert function snippet for a BST node:

fn insert(mut root: Option, val: i32) -> Option {
    if root.is_none() {
        return Some(Box::new(Node::new(val)));
    }
    if val < root.as_ref().unwrap().val {
        root.as_mut().unwrap().left = insert(root.as_mut().unwrap().left.take(), val);
    } else {
        root.as_mut().unwrap().right = insert(root.as_mut().unwrap().right.take(), val);
    }
    Some(root.unwrap())
}

What is the bug in this code?

medium

A. Calling unwrap() on root at the end consumes it, causing a move error

B. Not handling duplicate values explicitly

C. Using take() incorrectly on left and right children

D. Missing return statement in else branch

Solution

1. Step 1: Analyze unwrap() usage at function end

   root.unwrap() consumes root, but root is borrowed mutably earlier, causing move error.

2. Step 2: Correct approach for returning root

   Return root directly as Some(root) without unwrap to avoid move.

3. Final Answer:

   Calling unwrap() on root at the end consumes it, causing a move error -> Option A

4. Quick Check:

   unwrap() consumes Option, causes move error [OK]

Hint: Avoid unwrap() on Option when returning to prevent move errors [OK]

Common Mistakes:

• Ignoring move semantics of unwrap()
• Thinking take() is incorrect here
• Assuming missing return in else branch

5. You want to insert a list of values [20, 10, 30, 25, 35, 5] into an empty BST using Rust. After all insertions, which of the following represents the correct pre-order traversal output?

hard

A. [5, 10, 20, 25, 30, 35]

B. [10, 5, 20, 25, 30, 35]

C. [20, 30, 25, 35, 10, 5]

D. [20, 10, 5, 30, 25, 35]

Solution

1. Step 1: Insert values step-by-step

   Insert 20 as root; 10 left of 20; 30 right of 20; 25 left of 30; 35 right of 30; 5 left of 10.

2. Step 2: Perform pre-order traversal

   Pre-order visits root, left subtree, right subtree: 20, 10, 5, 30, 25, 35.

3. Final Answer:

   [20, 10, 5, 30, 25, 35] -> Option D

4. Quick Check:

   Pre-order = root-left-right [OK]

Hint: Pre-order = root, left subtree, then right subtree [OK]

Common Mistakes:

• Confusing pre-order with in-order traversal
• Inserting nodes in wrong positions
• Listing sorted values instead of traversal order