//BST
class Node
{   Node left, right;
    int data;
}//class node

public class BST
{   void displayPreorder(Node root)
    {   if(root!=null)
        {   System.out.print(root.data+" ");
            displayPreorder(root.left);
            displayPreorder(root.right);
        }
    }//display Preorder
    //*************************
    Node createRoot(int item)
    {   Node root=new Node();
        root.data=item;
        root.left=root.right=null;
        return root;
    }//createRoot
    //*************************
    void insert(Node root, int item)
    {   if(root!=null)
        {   if(item<root.data)
            {   if(root.left==null)
                {   Node temp=new Node();
                    temp.data=item;
                    temp.left=temp.right=null;
                    root.left=temp;
                }
                else
                    insert(root.left, item);
            }
            else if(item>root.data)
            {   if(root.right==null)
                {   Node temp=new Node();
                    temp.data=item;
                    temp.left=temp.right=null;
                    root.right=temp;
                }
                else
                    insert(root.right, item);
                }//else
                else if(item==root.data)
                {   System.out.println("No duplicates allowed");
                }
            }//if(root!=null)
        }//create
    //*************************
    boolean search(Node root, int item)
    {   boolean found=false;
        if(root!=null)
        {   if(item==root.data)
                found=true;
            else if(item<root.data)
                return search(root.left, item);
            else if(item>root.data)
                return search(root.right, item);
        }
        return found;
    }//search
    //*************************
    void delete(Node root, int item)
    {   if(root!=null)
        {   if(root.right.data==item)
            {   Node temp=root.right;
                if(temp.right==null && temp.left==null)
                {   root.right=null;
                }
                else if(temp.right==null)
                {   root.right=temp.left;
                }
                else if(temp.left==null)
                {   root.right=temp.right;
                }
                else
                {   root.right.data=temp.right.data;
                    delete(temp, temp.right.data);
                }
            }
            else if(root.left.data==item)
            {   Node temp=root.left;
                if(temp.right==null && temp.left==null)
                {   root.left=null;
                }
                if(temp.right==null)
                {   root.left=temp.left;
                }
                else if(temp.left==null)
                { root.left=temp.right;
                }
                else
                {   root.left.data=temp.left.data;
                    delete(temp, temp.left.data);
                }
            }
            else if(item>root.data)
            {   delete(root.right, item);
            }
            else if(item<root.data)
            {   delete(root.left, item);
            }
        }//if
    }//delete
    //*************************
    void deleteRoot(Node root)
    {   if(root.right==null && root.left==null)
        {   root=null;
        }
        else if(root.right==null)
        {   root=root.left;
        }
        else if(root.left==null)
        {   root=root.right;
        }
        else
        {   root.data=root.right.data;
            delete(root, root.data); 
        }
    }//deleteRoot
    //*************************
    public static void main(String args[])
    {   BST bst=new BST();
        Node root;
        root=bst.createRoot(5);
        bst.insert(root,3);
        bst.insert(root,4);
        bst.insert(root,8);
        bst.insert(root,9);
        bst.insert(root,7);
        System.out.println("Preorder traversal");
        bst.displayPreorder(root);
        System.out.println();
        System.out.println(bst.search(root, 9));
        System.out.println(bst.search(root, 1));
        bst.delete(root, 8);
        bst.displayPreorder(root);
        bst.deleteRoot(root);
        System.out.println();
        bst.displayPreorder(root);
    }//main
}//class BST
 /*
Preorder traversal
5 3 4 8 7 9
true
false
5 3 4 9 7
9 3 4 7
*/