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.