BST Delete Operation in DSA Go - Execution Trace

Concept Flow - BST Delete Operation

Start at root

↓

Find node to delete

↓

Node found?

No→Stop: Node not found

Yes↓

Check node children

↓

No child

↓

Delete

↓

Replace node data

↓

Delete inorder successor

↓

Done

The delete operation in a BST finds the node, then deletes or replaces it based on its children count.

Execution Sample

DSA Go

func deleteNode(root *Node, key int) *Node {
  if root == nil { return nil }
  if key < root.val {
    root.left = deleteNode(root.left, key)
  } else if key > root.val {
    root.right = deleteNode(root.right, key)
  } else {
    // delete logic
  }
  return root
}

This code recursively finds the node with the key and deletes it according to BST rules.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Tree State
1	Start at root	50	None	┌────────┐ │ 50 │ │ / \ │ │30 70 │ └────────┘
2	Go left (key=30 < 50)	30	None	┌────────┐ │ 50 │ │ / \ │ │30 70 │ └────────┘
3	Go left (key=30 == 30)	30	None	┌────────┐ │ 50 │ │ / \ │ │30 70 │ └────────┘
4	Node 30 has two children	30	None	┌────────┐ │ 50 │ │ / \ │ │30 70 │ └────────┘
5	Find inorder successor (min in right subtree of 30)	35	None	┌────────┐ │ 50 │ │ / \ │ │30 70 │ │ \ │ │ 35 │ └────────┘
6	Replace 30's value with 35	30	30.val = 35	┌────────┐ │ 50 │ │ / \ │ │35 70 │ │ \ │ │ 35 │ └────────┘
7	Delete inorder successor node 35	35	Remove node 35	┌────────┐ │ 50 │ │ / \ │ │35 70 │ └────────┘
8	Return updated root	50	None	┌────────┐ │ 50 │ │ / \ │ │35 70 │ └────────┘

💡 Deletion complete; node with key 30 replaced by inorder successor 35 and successor node removed.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 6	Final
current node	50	30	35	35	50
root.left.val	30	30	30	35	35
inorder successor	nil	nil	35	35	nil
tree size	7 nodes	7 nodes	7 nodes	7 nodes	6 nodes

Key Moments - 3 Insights

Why do we replace the node's value with the inorder successor's value instead of just deleting the node?

Because the node has two children, deleting it directly would break the BST structure. Replacing its value with the inorder successor (smallest node in right subtree) keeps the BST property intact. See steps 5 and 6 in the execution_table.

What happens if the node to delete has only one child?

The node is replaced directly by its child pointer, maintaining the BST structure. This is simpler than the two-children case. This scenario is not shown here but follows the same pointer update logic as in step 7.

Why do we delete the inorder successor node after copying its value?

Because the inorder successor's value is copied to the target node, the successor node becomes a duplicate and must be removed. It always has at most one child, so deletion is simpler. See step 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of root.left after replacement?

A 30

B 35

C 50

D 70

💡 Hint

Check the 'Pointer Changes' and 'Tree State' columns at step 6 in execution_table.

At which step is the inorder successor node removed from the tree?

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for the 'Remove node 35' action in the 'Pointer Changes' column.

If the node to delete had no children, how would the tree state change?

A Node is replaced by its only child

B Node is simply removed with no replacement

C Node value replaced by inorder successor

D Tree remains unchanged

💡 Hint

Refer to the concept_flow where 'No child' case leads to direct deletion.

Concept Snapshot

BST Delete Operation:
- Find node to delete by comparing keys
- If no children: remove node
- If one child: replace node with child
- If two children: replace node value with inorder successor
- Delete inorder successor node
- Maintain BST property after deletion

Full Transcript

The BST delete operation starts at the root and searches for the node with the given key. If the node is not found, the operation stops. When found, the deletion depends on the number of children. If the node has no children, it is simply removed. If it has one child, it is replaced by that child. If it has two children, the node's value is replaced by its inorder successor's value (the smallest node in its right subtree), then the inorder successor node is deleted. This preserves the BST property. The execution table shows a step-by-step deletion of node 30, which has two children. The inorder successor 35 replaces 30's value, then node 35 is removed. The variable tracker shows pointer and value changes. Key moments clarify why replacement is needed and how deletion works for different child cases. The visual quiz tests understanding of these steps.

Practice

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

easy

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

B. The entire tree is rebuilt from scratch.

C. The node is simply removed without affecting other nodes.

D. The root node is always changed.

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, simply remove the node and update its parent's pointer to null.

3. Final Answer:

   The node is simply removed without affecting other nodes. -> Option C

4. Quick Check:

   Leaf node deletion = simple removal [OK]

Hint: Leaf nodes delete by direct removal only [OK]

Common Mistakes:

• Thinking children need rearrangement
• Assuming root always changes
• Believing tree rebuild is needed

2. Which of the following Go function signatures correctly represents a BST delete operation for a node with integer keys?

easy

A. func deleteNode(key int, root *Node) *Node

B. func deleteNode(root *Node, key int) *Node

C. func deleteNode(root Node, key int) Node

D. func deleteNode(root *Node, key string) *Node

Solution

1. Step 1: Check parameter order and types

   The root node pointer should be first, key integer second, returning updated root pointer.

2. Step 2: Validate pointer usage and key type

   Root must be a pointer to allow tree modification; key must be int for integer keys.

3. Final Answer:

   func deleteNode(root *Node, key int) *Node -> Option B

4. Quick Check:

   Correct signature = root pointer first, int key [OK]

Hint: Root pointer first, int key second, returns updated root [OK]

Common Mistakes:

• Swapping parameter order
• Using value instead of pointer for root
• Using wrong key type

3. Given the BST below and the Go code to delete node with key 10, what is the in-order traversal output after deletion? BST structure: 15 / \ 10 20 / \ 8 12 Go code snippet:

root = deleteNode(root, 10)

medium

A. [12, 15, 20]

B. [8, 15, 20]

C. [8, 10, 12, 15, 20]

D. [8, 12, 15, 20]

Solution

1. Step 1: Identify node to delete and its children

   Node 10 has two children: 8 (left) and 12 (right).

2. Step 2: Replace node 10 with its in-order successor

   In-order successor is 12. Replace 10 with 12, then delete original 12 node.

3. Step 3: Perform in-order traversal after deletion

   Traversal order: 8, 12, 15, 20.

4. Final Answer:

   [8, 12, 15, 20] -> Option D

5. Quick Check:

   In-order after deleting 10 = [8, 12, 15, 20] [OK]

Hint: Replace deleted node with in-order successor [OK]

Common Mistakes:

• Deleting successor node incorrectly
• Skipping replacement step
• Confusing in-order predecessor with successor

4. Consider this Go code snippet for deleting a node from a BST. What is the bug?

func deleteNode(root *Node, key int) *Node {
    if root == nil {
        return nil
    }
    if key < root.key {
        root.left = deleteNode(root.left, key)
    } else if key > root.key {
        root.right = deleteNode(root.right, key)
    } else {
        if root.left == nil {
            return root.right
        } else if root.right == nil {
            return root.left
        }
        temp := findMin(root.right)
        root.key = temp.key
        deleteNode(root.right, temp.key)
    }
    return root
}

medium

A. Missing assignment of root.right after deleting successor node.

B. Incorrect base case for empty tree.

C. Wrong comparison operators for key checks.

D. Returning nil instead of root in all cases.

Solution

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

   After replacing root.key with successor's key, the successor node must be deleted from right subtree.

2. Step 2: Check recursive call effect on tree structure

   The call deleteNode(root.right, temp.key) is made but its result is not assigned back to root.right, so the successor node remains.

3. Final Answer:

   Missing assignment of root.right after deleting successor node. -> Option A

4. Quick Check:

   Assign recursive delete result to root.right [OK]

Hint: Always assign recursive delete results to child pointers [OK]

Common Mistakes:

• Ignoring returned subtree after deletion
• Not updating pointers after recursive calls
• Confusing base case with recursive case

5. You have a BST with nodes: 30, 20, 40, 10, 25, 35, 50. You delete node 30 (root). Which node becomes the new root after deletion using the standard BST delete operation?

hard

A. Node 35 (in-order successor)

B. Node 25 (in-order predecessor)

C. Node 40 (right child)

D. Node 20 (left child)

Solution

1. Step 1: Identify node to delete and its children

   Node 30 is root with two children: left subtree (20) and right subtree (40).

2. Step 2: Find in-order successor of node 30

   In-order successor is the smallest node in right subtree, which is 35.

3. Step 3: Replace root with in-order successor

   Replace 30 with 35, then delete original 35 node from right subtree.

4. Final Answer:

   Node 35 (in-order successor) -> Option A

5. Quick Check:

   Root replaced by in-order successor = 35 [OK]

Hint: Root replaced by smallest node in right subtree [OK]

Common Mistakes:

• Using in-order predecessor instead of successor
• Choosing direct child without successor check
• Not deleting successor node after replacement