import java.util.*;
public class BinarySearchTree3 
{
 class Node {
 int key;
 Node left, right;
 public Node(int item) {
 key = item;
 left = right = null;
 }
 }
 private Node root;
 public BinarySearchTree3() 
 {
root = null;
 }
 public void insert(int key) 
 { root = insertKey(root, key); }
 private Node insertKey(Node root, int key) 
 { if (root == null) 
 {
 root = new Node(key);
 return root;
 }
 if (key < root.key)
 root.left = insertKey(root.left, key);
 else if (key > root.key)
 root.right = insertKey(root.right, key);
 return root;
 }
 public void inorder() {
 inorderRec(root);
 }
 private void inorderRec(Node root) {
 if (root != null) {
 inorderRec(root.left);
 System.out.print(root.key + " ");
 inorderRec(root.right);
 }
 }
 public void deleteKey(int key) 
 { root = deleteRec(root, key); }
 private Node deleteRec(Node root, int key) 
 { if (root == null)
 return root;
 if (key < root.key)
 root.left = deleteRec(root.left, key);
 else if (key > root.key)
 root.right = deleteRec(root.right, key);
 else 
{ if (root.left == null)
 return root.right;
 else if (root.right == null)
 return root.left;
 
 root.key = minValue(root.right);
 root.right = deleteRec(root.right, root.key);
 }
 return root;
 }
 
 public int minValue(Node root) {
 int minv = root.key;
 while (root.left != null) {
 minv = root.left.key;
 root = root.left;
 }
 return minv;
 }
 
 public static void main(String[] args) 
 {
Scanner sc = new Scanner(System.in);
BinarySearchTree3 bst = new BinarySearchTree3();
String ch="";
do{
System.out.print("Enter the element to be inserted in the tree: ");
int n=sc.nextInt();
sc.nextLine();
bst.insert(n);
System.out.print("Do you want to insert another element? (Say 'yes'): ");
ch = sc.nextLine();
}while(ch.equals("yes"));
System.out.println();
System.out.print("Inorder Traversal : The elements in the tree are: ");
bst.inorder();
System.out.println();
System.out.print("Enter the element to be removed from the tree: ");
int r=sc.nextInt();
sc.nextLine();
System.out.println();
bst.deleteKey(r);
System.out.print("Inorder traversal after deletion of "+r);
bst.inorder();
System.out.println();
 }
}