public class BinarySearchTree extends BinaryTree
{
    public BinarySearchTree()
    //default constructor
    //postcondition:root=null
    {
        //Write the method definition here
    }
    public Boolean search(int searchItem)
    //method to determine whether searchItem is in binary search
    //tree
    //postcondition: A node is created and inserted in the binary
    //tree
    {
        return search(searchItem,root);
    }
    public Boolean search(int searchItem,BinaryTreeNode root){
        if(root==null){
            return false;
        }
        if(searchItem==root.data){
            return true;
        }
        else if(searchItem<root.data){
            return search(searchItem,root.left);
        }
        else{
            return search(searchItem,root.right);
        }
    }
    public void insert(int searchItem)
    //method to determine whether searchItem is in binary search
    //tree
    //post condition: A node is created and inserted in the binary
    //tree
    {
        if(search(searchItem)){
            System.err.println("Item alredy exist");
        }
        else{
            insertNode(searchItem);
        }
    }
    public void deleteNode(int deleteItem)
    //method to delete deleteItem from the binary tree.
    //postcondition: if a node with the same info as deleteItem is
    //found, it is deleted from the binary tree.
    {
        deleteNode(deleteItem,root);
    }
    private  BinaryTreeNode deleteNode(int deleteItem, BinaryTreeNode root){

        if(root==null){
            return null;
        }
        if(deleteItem<root.data){
            root.left=deleteNode(deleteItem,root.left);
        }
        else if(deleteItem>root.data){
            root.right=deleteNode(deleteItem,root.right);
        }
        else{

            if(root.left==null&&root.right==null){
                root=null;
            }
            else if(root.left==null){
                root=root.right;
            }
            else if(root.right==null){
                root=root.left;
            }
            else{

                BinaryTreeNode leftMost=root.right;
                if(leftMost.left==null){
                    root.data=leftMost.data;
                    root.right = leftMost.right;
                }
                else{
                    BinaryTreeNode current=root;
                    while(leftMost.left!=null){
                        current=leftMost;
                        leftMost=leftMost.left;
                    }
                    root.data=leftMost.data;
                    current.left = leftMost.right;
                }

            }

        }
        return root;
    }
}