import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
import java.util.*;

//implement tree using linked list



public class Main {
    static class Node{
        //member variables
        int data;
        Node left;
        Node right;
    
        //constructor
        Node(int val){
            this.data = val;
            this.left = null;
            this.right = null;
        }
    }
    static Node root=null;


    static Node findMinNode(Node temp){
        if(temp.left==null)
            return temp;
        else
            return findMinNode(temp.left);
    }
    static Node delete(int val, Node root){
        if(root==null)
            return null;

        if(val<root.data)
            root.left = delete(val,root.left);
        else{
            if(val>root.data)
                root.right = delete(val,root.right);
            else{
                //node with two child 
                if(root.right!=null && root.left!=null){
                    Node temp = root;
                    Node minValNode = findMinNode(temp.right);
                    root.data = minValNode.data;
                    root.right = delete(minValNode.data, root.right);
                }
                //node with one child
                else if(root.left!=null){
                    root = root.left;
                }else if(root.right!=null){
                    root = root.right;
                }
                //no child - leaf node
                else{
                    root = null;
                }
            }
        }
        return root;
    }

    static Node insert(int val,Node root){
        if(root==null){
           root = new Node(val);
           return root;
        }
        //if root is not null 
        else{
            if(val<root.data) //2 < 11
            {
                root.left =  insert(val,root.left);
                // 11.left = insert (2, 11.left);
            }
            else{
                root.right = insert(val,root.right);
            }
        }      
        return root;
    }

    static boolean search(int val, Node root){
        if(root==null)
            return false;
    
        if(root.data == val){
            return true;
        }
        else{
            if(val<root.data){
                return search(val,root.left);
            }
            else{
                return search(val,root.right);
            }
        }
    }

    static void inorder(Node root){
        // left child, root ,right child
        if(root!=null){
            inorder(root.left);
            System.out.println(root.data);
            inorder(root.right);
        }
        return;
    }


    static void preorder(Node root){
        //root, left child, right child
        if(root!=null){
            System.out.println(root.data);
            preorder(root.left);
            preorder(root.right);
        }
        return;
     }


    static void postorder(Node root){
        //left child, right child, root
        if(root!=null){
            postorder(root.left);
            postorder(root.right);
            System.out.println(root.data);
        }
        return;
     }



    public static void main(String[] args) {
        int choice;
        Scanner sc= new Scanner(System.in);
        do{
            System.out.println("Select Choice : \n1. Insert\n2.Search\n3.Traverse\n4.Delete\n5.Exit");
            choice = sc.nextInt();
            int data;
            switch(choice){
                case 1: System.out.println("Enter new element to insert in tree : ");
                        data = sc.nextInt();
                        root = insert(data,root);
                        break;
                case 2: System.out.println("Enter element to search in tree : ");
                        data = sc.nextInt();
                        System.out.println ("Result of search operation " + search(data,root));
                        break;
                case 3: System.out.println("Visiting nodes of tree in inorder sequence : ");
                        inorder(root);
                        System.out.println("Visiting nodes of tree in preorder sequence : ");
                        preorder(root);
                        System.out.println("Visiting nodes of tree in postorder sequence : ");
                        postorder(root);
                        break;
                case 4: System.out.println("Enter element to delete from tree : ");
                        root = delete(sc.nextInt(),root);
                        break;
            }
        }while(choice!=5);
        sc.close();
    }
}