❌ Deletion in Binary Search Tree (BST)

Follow Me

🧠 Deletion Rules:

There are 3 cases when deleting a node:

1️⃣ Leaf Node (No children)

👉 Just remove the node.

2️⃣ One child

👉 Replace the node with its only child.

3️⃣ Two children

👉 Replace the node with its in-order successor (smallest value in right subtree) or in-order predecessor (largest in left subtree).

🪴 Example BST:

We’ll use this tree:

50 / \ 30 70 / \ / \ 20 40 60 80

🔧 Case-wise Deletion:

✅ Case 1: Delete Leaf Node 20

• 20 has no children

• Simply remove it

50 / \ 30 70 \ / \ 40 60 80

✅ Case 2: Delete Node 30 (one child)

• 30 has only one child: 40

• Replace 30 with 40

50 / \ 40 70 / \ 60 80

✅ Case 3: Delete Node 50 (two children)

• 50 has 2 children

• In-order successor = 60

• Replace 50 with 60, then delete 60 from right subtree

60 / \ 40 70 \ 80

🧠 Python Code:

def delete(root, key): if root is None: return root if key < root.val: root.left = delete(root.left, key) elif key > root.val: root.right = delete(root.right, key) else: if root.left is None: return root.right elif root.right is None: return root.left temp = find_min(root.right) root.val = temp.val root.right = delete(root.right, temp.val) return root def find_min(node): while node.left: node = node.left return node

📌 Summary Table:

Case	Condition	Action
Case 1	No child	Remove node
Case 2	One child	Replace with child
Case 3	Two children	Replace with in-order successor