Deletion in a Binary Search TreeWrite a program to delete an element from a Binary Search Tree (BST). The program should first allow the user to input elements to construct the BST until they enter -1 to stop. Then, it should prompt the user for an element to delete and print the inorder traversal of the BST after deletion.Constraints:NAExample:Sample Input:5030702040-130Sample Output:20 40 50 70 Explanation:Input: 50 30 70 20 40 -1Delete: 30Output: 20 40 50 70Public Test Cases:# INPUT EXPECTED OUTPUT1 5030702040-13020 40 50 70

Here is a Python solution for the problem:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val),
        inorder(root.right)

def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, 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.val:
        root.left = deleteNode(root.left, key)
    elif(key > root.val):
        root.right = deleteNode(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        root.val = minValueNode(root.right).val
        root.right = deleteNode(root.right, root.val)
    return root

r = None
while True:
    i = int(input())
    if i == -1:
        break
    r = insert(r, i)

key = int(input())
r = deleteNode(r, key)

inorder(r)

This program first creates a binary search tree from the user's input. It then deletes the specified node and prints the inorder traversal of the tree. The deletion is handled by finding the inorder successor (smallest in the right subtree) of the node to be deleted and replacing the node's value with the successor's value. Then the successor node is deleted. If the node to be deleted has only one child or no children, then the child or NULL is returned to the parent of the node to be deleted.