BST Delete Operation in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current node is None in the delete function.

DSA Rust

if root [1] {
    return root;
}

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

A== None

B!= None

C== Some

D!= Some

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!= None' instead of '== None' causes the function to continue incorrectly.

Using '== Some' is invalid syntax for Option.

We check if the root is None to stop recursion when the node is not found.

2fill in blank

medium

Complete the code to move left or right in the BST based on the key comparison.

DSA Rust

if key < root.as_ref().unwrap().val {
    root.as_mut().unwrap().left = Self::delete_node(root.as_mut().unwrap().left.take(), key);
} else if key > root.as_ref().unwrap().val {
    root.as_mut().unwrap().right = Self::delete_node(root.as_mut().unwrap().right.take(), [1]);
}

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

Akey

Broot.val

Croot.as_ref().unwrap().val

Droot.left

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'root.val' or 'root.left' causes errors because root is an Option and needs unwrapping.

Using the node's value instead of the key to continue searching is incorrect.

We continue searching for the key to delete by comparing with the current node's value.

3fill in blank

hard

Fix the error in the code to find the minimum node in the right subtree.

DSA Rust

fn min_value_node(mut node: Option<Box<TreeNode>>) -> Option<Box<TreeNode>> {
    while node.as_ref().unwrap().left.is_some() {
        node = node.as_mut().unwrap().left.take();
    }
    [1]
}

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

Anode.as_ref()

Bnode.unwrap()

Cnode

Dnode.as_mut()

Attempts:

3 left

💡 Hint

Common Mistakes

Using unwrap() here consumes the Option and causes errors.

Using as_ref() or as_mut() returns references, not ownership.

Return the node itself after reaching the leftmost node.

4fill in blank

hard

Fill both blanks to replace the current node with its right child when left child is None.

DSA Rust

if root.as_ref().unwrap().left.is_none() {
    let temp = root.as_mut().unwrap().right.take();
    [1] = None;
    [2] = temp;
    return [2];
}

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

Aroot

Btemp

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning temp to None or mixing variable names causes errors.

Not setting root to None before reassigning causes ownership issues.

We set root to None and then assign temp (right child) to root to delete the current node.

5fill in blank

hard

Fill all three blanks to replace the current node's value with the minimum node's value and delete that minimum node.

DSA Rust

let min_node = Self::min_value_node(root.as_ref().unwrap().right.clone()).unwrap();
root.as_mut().unwrap().val = [1];
root.as_mut().unwrap().right = Self::delete_node(root.as_mut().unwrap().right.take(), [2]);
return [3];

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

Amin_node.val

Croot

Dmin_node

Attempts:

3 left

💡 Hint

Common Mistakes

Returning min_node instead of root breaks the tree structure.

Using wrong variables for value replacement causes errors.

We copy the minimum node's value to current node, delete the minimum node from right subtree, and return root.

Practice

1. What happens when you delete a leaf node (a node with no children) from a Binary Search Tree (BST)?

easy

A. The entire tree is rebuilt from scratch.

B. The node's children replace it in the tree.

C. The node is simply removed with no further changes needed.

D. The tree becomes unbalanced and must be rebalanced immediately.

Solution

1. Step 1: Understand leaf node deletion

   A leaf node has no children, so removing it does not affect other nodes.

2. Step 2: Effect on BST structure

   Since no children exist, no rearrangement is needed; just remove the node.

3. Final Answer:

   The node is simply removed with no further changes needed. -> Option C

4. Quick Check:

   Leaf node deletion = simple removal [OK]

Hint: Leaf nodes delete by direct removal, no child rearrangement needed [OK]

Common Mistakes:

• Thinking children must replace the node
• Assuming tree rebalancing is always needed
• Confusing leaf with internal node deletion

2. Which of the following Rust function signatures correctly represents a BST node deletion method that returns the updated tree root?

easy

A. fn delete_node(root: Option, key: i32) -> Option

B. fn delete_node(root: &Node, key: i32) -> Node

C. fn delete_node(root: Box<Node>, key: i32) -> Box<Node>

D. fn delete_node(root: &mut Node, key: i32) -> &Node

Solution

1. Step 1: Understand Rust ownership for BST nodes

   BST nodes are often wrapped in Option to allow empty children and ownership transfer.

2. Step 2: Correct function signature for deletion

   Deletion may change the root, so returning Option is needed to reflect updated tree.

3. Final Answer:

   fn delete_node(root: Option, key: i32) -> Option -> Option A

4. Quick Check:

   Ownership and optional root = Option [OK]

Hint: Use Option for nullable owned nodes in Rust [OK]

Common Mistakes:

• Using references without ownership transfer
• Returning plain Node instead of Option
• Using &Node which is immutable reference

3. Given the BST with nodes [10, 5, 15, 3, 7, 12, 18], what is the in-order traversal output after deleting node 15?

medium

A. [3, 5, 7, 10, 12, 18]

B. [3, 5, 7, 10, 12]

C. [3, 5, 7, 10, 18]

D. [3, 5, 7, 10, 12, 15, 18]

Solution

1. Step 1: Identify node 15 deletion case

   Node 15 has two children: 12 (left) and 18 (right). We replace 15 with its in-order successor (minimum in right subtree), which is 18.

2. Step 2: Perform deletion and in-order traversal

   Replace 15 with 18, then remove original 18 node (leaf). The tree nodes become [10, 5, 18, 3, 7, 12]. In-order traversal is sorted: [3, 5, 7, 10, 12, 18].

3. Final Answer:

   [3, 5, 7, 10, 12, 18] -> Option A

4. Quick Check:

   In-order after deletion = sorted nodes without 15 [OK]

Hint: Replace deleted node with in-order successor for two children case [OK]

Common Mistakes:

• Removing 18 instead of replacing 15 with 18
• Forgetting to remove original successor node
• Incorrect in-order traversal order

4. Consider this Rust code snippet for BST deletion. What is the bug?

fn delete_node(root: Option<Box<Node>>, key: i32) -> Option<Box<Node>> {
    let mut node = root.unwrap();
    if key < node.val {
        node.left = delete_node(node.left, key);
    } else if key > node.val {
        node.right = delete_node(node.right, key);
    } else {
        if node.left.is_none() {
            return node.right;
        } else if node.right.is_none() {
            return node.left;
        }
        let min_node = find_min(node.right.as_ref().unwrap());
        node.val = min_node.val;
        node.right = delete_node(node.right, min_node.val);
    }
    Some(node)
}

medium

A. find_min should take ownership, not a reference.

B. Using unwrap() causes panic if root is None.

C. Returning node.right or node.left directly causes ownership errors.

D. The function does not handle the case when key equals node.val.

Solution

1. Step 1: Analyze None handling

   The code calls root.unwrap() without checking if root is None, causing a panic on empty tree.

2. Step 2: Correct handling

   Add "if root.is_none() { return None; }" before unwrap.

3. Final Answer:

   Using unwrap() causes panic if root is None. -> Option B

4. Quick Check:

   unwrap without None check = panic [OK]

Hint: Check Option::is_none() before unwrap() [OK]

Common Mistakes:

• Ignoring Rust ownership rules on Option
• Using unwrap() without checking None
• Misunderstanding reference vs ownership in find_min

5. You have a BST with nodes [20, 10, 30, 5, 15, 25, 35]. You delete node 10, which has two children. After deletion, what is the correct new in-order traversal of the BST?

hard

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

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

C. [5, 15, 20, 25, 30]

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

Solution

1. Step 1: Identify deletion of node with two children

   Node 10 has children 5 and 15. We replace 10 with its in-order successor, which is 15.

2. Step 2: Adjust tree and perform in-order traversal

   Replace 10 with 15, then remove original 15 node. The BST nodes become [20, 15, 30, 5, 25, 35]. In-order traversal is sorted: [5, 15, 20, 25, 30, 35].

3. Final Answer:

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

4. Quick Check:

   In-order after deletion = sorted nodes without 10 [OK]

Hint: Replace deleted node with in-order successor for two-child nodes [OK]

Common Mistakes:

• Leaving deleted node in traversal
• Not replacing with in-order successor
• Incorrect traversal order