# Deletion Operation in BST

### Insertion in BST

Deletion in a Binary Search Tree (BST) involves removing a node with a given key while maintaining the BST properties. The deletion operation can be performed in three cases:

Deleting a leaf node: If the node to be deleted is a leaf node (a node with no children), it can be simply removed from the tree.

Deleting a node with one child: If the node to be deleted has only one child, we can replace the node with its child.

Deleting a node with two children:

If the node to be deleted has two children, we need to find a replacement node that preserves the BST property.

This replacement node can be the node with the smallest key in the right subtree (successor) or the node with the largest key in the left subtree (predecessor).

Once we find the replacement node, we replace the node to be deleted with the replacement node, and then delete the replacement node from its original position.

Here is a step-by-step explanation of the deletion process in a BST:

Start at the root and traverse down the tree to find the node to be deleted.

If the key to be deleted is less than the current node's key, move to the left child. If the key is greater, move to the right child. Repeat this process until the node to be deleted is found or we reach a null node (end of the tree).

Once the node to be deleted is found, consider the following cases:

a. If the node is a leaf node (no children), simply remove the node from the tree.

b. If the node has one child, replace the node with its child.

c. If the node has two children, find the successor or predecessor node. Replace the node's key with the key of the successor/predecessor, and then recursively delete the successor/predecessor node from its original position.

After the deletion is complete, ensure that the BST properties are maintained by adjusting the tree if necessary.

## Example

Let's consider the following Binary Search Tree (BST) with the given keys: 10, 12, 16, 17, 18, 19, 15,20, 25 and root is 20

Let's delete the 15 from BST.

Initial BST:

20

/ \

15 25

/ \ \

10 18 30

/ \

17 19

/

16

To delete the key 15 from the BST, we follow these steps:

Starting at the root, we compare the key 15 with the current node's key, which is 20.

Since 15 is less than 20, we move to the left child of the current node.

We compare 15 with the key of the left child, which is 15.

As we have found the node to be deleted, we consider the following cases:

a. Case 1: If the node to be deleted is a leaf node (no children), we simply remove it from the tree. In this case, we can remove the node with key 15.

Final BST after deleting 15:

20

/ \

16 25

/ \ \

10 18 30

/ \

17 19

The deletion operation is complete, and the updated BST is shown above.

Note that after deleting the node with key 15, the BST property is still maintained, and the remaining nodes are correctly positioned in the tree.

## Code Snippet

Here's an example of Python code that demonstrates the deletion of a node in a Binary Search Tree (BST):

class Node:

def __init__(self, key):

self.key = key

self.left = None

self.right = None

def insert(root, key):

if root is None:

return Node(key)

if key < root.key:

root.left = insert(root.left, key)

elif key > root.key:

root.right = insert(root.right, key)

return root

def minValueNode(node):

current = node

while current.left is not None:

current = current.left

return current

def deleteNode(root, key):

if root is None:

return root

if key < root.key:

root.left = deleteNode(root.left, key)

elif key > root.key:

root.right = deleteNode(root.right, key)

else:

if root.left is None:

temp = root.right

root = None

return temp

elif root.right is None:

temp = root.left

root = None

return temp

temp = minValueNode(root.right)

root.key = temp.key

root.right = deleteNode(root.right, temp.key)

return root

def inorder(root):

if root:

inorder(root.left)

print(root.key, end=" ")

inorder(root.right)

# Create a BST

root = None

root = insert(root, 20)

root = insert(root, 15)

root = insert(root, 25)

root = insert(root, 10)

root = insert(root, 18)

root = insert(root, 30)

root = insert(root, 16)

root = insert(root, 19)

# Print the inorder traversal of the BST before deletion

print("Inorder traversal before deletion:")

inorder(root)

print()

# Delete a node with key 15 from the BST

root = deleteNode(root, 15)

# Print the inorder traversal of the BST after deletion

print("Inorder traversal after deletion:")

inorder(root)

print()

This code demonstrates the insertion of nodes into a BST using the insert function, deletion of a node using the deleteNode function, and printing the inorder traversal of the BST using the inorder function.