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: 


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

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.

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:

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.