BST Delete Operation in DSA Rust - Execution Trace

Concept Flow - BST Delete Operation

Start at root

↓

Compare key with current node

↓

Key < node

↓

Go left

↓

Found node to delete?

↓

No

↓

Stop

↓

Replace node value

↓

Delete successor

↓

Done

The delete operation in a BST searches for the node, then deletes it based on whether it is a leaf, has one child, or two children, adjusting pointers accordingly.

Execution Sample

DSA Rust

fn delete_node(root: Option<Box<Node>>, key: i32) -> Option<Box<Node>> {
    if root.is_none() { return None; }
    let mut root = root.unwrap();
    if key < root.val {
        root.left = delete_node(root.left.take(), key);
    } else if key > root.val {
        root.right = delete_node(root.right.take(), key);
    } else {
        // deletion cases
    }
    Some(root)
}

This code recursively finds the node with the key and deletes it, handling different cases.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root (50), compare key=30	50	None	┌────────┐ ┌────────┐ ┌────────┐ │ val:50 │ │ val:30 │ │ val:70 │ │ left───┼──→ │ left───┼→ ∅ │ right──┼→ ∅ └────────┘ └────────┘ └────────┘ root
2	Key 30 < 50, go left to 30	30	None	┌────────┐ ┌────────┐ ┌────────┐ │ val:50 │ │ val:30 │ │ val:70 │ │ left───┼──→ │ left───┼→ ∅ │ right──┼→ ∅ └────────┘ └────────┘ └────────┘ root
3	Found node 30 to delete (leaf)	30	Parent's left pointer set to None	┌────────┐ ┌────────┐ │ val:50 │ │ val:70 │ │ left───┼──→ │ left───┼→ ∅ │ right──┼──→ │ right──┼→ ∅ └────────┘ └────────┘ root
4	Deletion complete, return updated tree	50	None	┌────────┐ ┌────────┐ │ val:50 │ │ val:70 │ │ left───┼──→ │ left───┼→ ∅ │ right──┼──→ │ right──┼→ ∅ └────────┘ └────────┘ root

💡 Node with key 30 found and deleted; it was a leaf node.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
root	Node(50)	Node(50)	Node(50)	Node(50)	Node(50)
current_node	Node(50)	Node(50)	Node(30)	Node(30)	None (deleted)
parent.left	Node(30)	Node(30)	Node(30)	None	None

Key Moments - 3 Insights

Why do we set the parent's left pointer to None when deleting a leaf node?

Because the leaf node has no children, removing it means the parent's pointer must no longer reference it. See execution_table step 3 where parent's left pointer changes to None.

What happens if the node to delete has two children?

We find the inorder successor (smallest node in right subtree), replace the node's value with successor's, then delete the successor node. This is not shown in this example but is part of the delete operation flow.

Why do we return the updated subtree after deletion?

Because the recursive call may change the subtree's root (like deleting the root node), so we must update the parent's pointer to the new subtree root. See execution_table step 4 where updated tree is returned.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what pointer change happens?

A Parent's left pointer set to None

B Root pointer set to None

C Node 30's right pointer set to None

D Node 50's right pointer set to None

💡 Hint

Check the 'Pointer Changes' column in execution_table row for step 3.

At which step does the node with key 30 get deleted?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Operation' and 'Visual State' columns in execution_table to see when deletion occurs.

If the node to delete had one child, how would the pointer change differ at step 3?

A Parent's pointer would point to the child node

B Parent's pointer would be set to None

C Root pointer would be set to None

D No pointer changes needed

💡 Hint

Recall that deleting a node with one child requires linking the parent directly to that child.

Concept Snapshot

BST Delete Operation:
- Search node by comparing keys
- If leaf: remove node, set parent's pointer to None
- If one child: link parent to child
- If two children: replace with inorder successor
- Return updated subtree after deletion

Full Transcript

The BST delete operation starts at the root and compares the key to delete with the current node's value. If the key is less, it moves left; if more, it moves right. When the node to delete is found, three cases arise: if it's a leaf, it is simply removed by setting the parent's pointer to None; if it has one child, the parent links directly to that child; if it has two children, the node's value is replaced with its inorder successor's value, and the successor node is deleted recursively. After deletion, the updated subtree is returned to maintain correct links. This process ensures the BST properties remain intact.

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