BST Delete Operation in DSA Rust - Build from Scratch

BST Delete Operation

📖 Scenario: You are managing a collection of unique numbers using a Binary Search Tree (BST). Sometimes, you need to remove a number from this collection while keeping the tree organized.Imagine a phone book where you want to delete a contact but keep the list sorted for quick searching.

🎯 Goal: Build a Rust program that creates a BST, sets up a root node, implements the delete operation for a given value, and prints the tree in order after deletion.

📋 What You'll Learn

Create a BST node struct with integer values and optional left and right children.

Create a root node with specific values and children.

Add a variable to hold the value to delete from the BST.

Implement the delete function for the BST that removes the node with the given value.

Print the BST in-order after deletion to show the updated tree.

💡 Why This Matters

🌍 Real World

BSTs are used in databases, file systems, and search engines to organize data for fast insertion, deletion, and lookup.

💼 Career

Understanding BST operations is essential for software engineers working on data storage, retrieval systems, and performance optimization.

1

Create the BST Node and Initial Tree

Create a struct called Node with fields value: i32, left: Option>, and right: Option>. Then create a root variable of type Option> representing this tree:
5
/ \
3 7
/ / \
2 6 8

DSA Rust

// Your code here

Hint

Define the Node struct first. Then create root as an Option> with nested nodes matching the tree diagram.

2

Add the Value to Delete

Add a variable called delete_val of type i32 and set it to 3. This is the value you will remove from the BST.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn main() {
    let root = Some(Box::new(Node {
        value: 5,
        left: Some(Box::new(Node {
            value: 3,
            left: Some(Box::new(Node {
                value: 2,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 7,
            left: Some(Box::new(Node {
                value: 6,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 8,
                left: None,
                right: None,
            })),
        })),
    }));
    // Add delete_val variable here
    // Your code here
}

Hint

Declare delete_val as an i32 and assign it the value 3.

3

Implement the BST Delete Function

Write a function called delete_node that takes root: Option> and key: i32 and returns Option>. Implement the BST delete logic:
- If the node is None, return None.
- If key is less than node's value, recursively delete in left subtree.
- If key is greater, recursively delete in right subtree.
- If key equals node's value:
- If node has no children, return None.
- If node has one child, return that child.
- If node has two children, replace node's value with the minimum value in the right subtree, then delete that minimum node.
Use a helper function min_value_node to find the minimum node in a subtree.

DSA Rust

struct Node {
    value: i32,
    left: Option>,
    right: Option>,
}

fn min_value_node(mut node: &Box) -> i32 {
    // Your code here
}

fn delete_node(root: Option>, key: i32) -> Option> {
    // Your code here
}

fn main() {
    let root = Some(Box::new(Node {
        value: 5,
        left: Some(Box::new(Node {
            value: 3,
            left: Some(Box::new(Node {
                value: 2,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 7,
            left: Some(Box::new(Node {
                value: 6,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 8,
                left: None,
                right: None,
            })),
        })),
    }));
    let delete_val: i32 = 3;
}

Hint

Use recursion to find the node to delete. Handle three cases: no children, one child, two children. Use min_value_node to find the smallest value in the right subtree.

4

Delete the Node and Print In-Order Traversal

Call delete_node with root and delete_val to get the updated tree. Then write a function inorder that prints the BST values in ascending order separated by spaces. Finally, print the in-order traversal of the updated tree.

DSA Rust

fn inorder(root: &Option>) {
    // Your code here
}

fn main() {
    let root = Some(Box::new(Node {
        value: 5,
        left: Some(Box::new(Node {
            value: 3,
            left: Some(Box::new(Node {
                value: 2,
                left: None,
                right: None,
            })),
            right: None,
        })),
        right: Some(Box::new(Node {
            value: 7,
            left: Some(Box::new(Node {
                value: 6,
                left: None,
                right: None,
            })),
            right: Some(Box::new(Node {
                value: 8,
                left: None,
                right: None,
            })),
        })),
    }));
    let delete_val: i32 = 3;
    // Call delete_node and print inorder traversal
    // Your code here
}

Hint

Call delete_node(root, delete_val) and store the result. Then write inorder to print values in ascending order separated by spaces. Finally, print a newline.

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