class BinaryTreeNode {
    int element;
    BinaryTreeNode left;
    BinaryTreeNode right;
    public BinaryTreeNode(int theElement) {
	element = theElement;
        left = null;
        right = null;
    }
}

class BinarySearchTree {
    BinaryTreeNode root;

    public BinarySearchTree(){
	root = null;
    }

    public boolean search(int theElement) 
    {
	BinaryTreeNode x = root;
        while (x != null) {
	    if (x.element == theElement) return true;
            if (x.element < theElement) x = x.right;
            else x = x.left;
	}
        return false;
    }

    public void insert(int theElement)
    { 
        if (root == null) {
	    root = new BinaryTreeNode(theElement);
            return;
	}
	BinaryTreeNode x = root;
        boolean done = false;
        while (! done) {
	    if (x.element == theElement) return;
            if (x.element < theElement) {
		if (x.right == null) 
		    {
			x.right = new BinaryTreeNode(theElement);
                        done = true;
                    }
		else 
                    { x = x.right; }
	    }
	    else {
                if (x.left == null) {
		    x.left = new BinaryTreeNode(theElement);
                    done = true;
		}
                else
                    { x = x.left;}
            }
	} 
    }


    public void recInsert(int theElement)
    { 
	root = recInsert(theElement, root);
    }

    private BinaryTreeNode recInsert(int x, BinaryTreeNode t)
    {
        BinaryTreeNode temp;

        if (t == null) return new BinaryTreeNode(x);

        if (x == t.element) return t;

        if (x > t.element) 
	    { 
		temp = recInsert(x, t.right);
                t.right = temp;
            }
        else
            {
                temp = recInsert(x, t.left);
                t.left = temp;
            }
        return t;
    } 

    public void delete(int theElement)
    {
	root = delete(theElement, root);
    }

    private BinaryTreeNode findMin(BinaryTreeNode t)
    { 
	if (t != null) {
	    while (t.left != null) {
		t = t.left;
	    }

	}

        return t;
    }

    private BinaryTreeNode delete(int x, BinaryTreeNode t)
    {

        if (t == null) return t;

        if (x < t.element) 
	    t.left = delete(x, t.left);
        else if (x > t.element)
            t.right = delete(x, t.right);
        else if (t.left == null)
            t = t.right;
        else if (t.right == null)
            t = t.left;
        else {
            t.element = findMin(t.right).element;
            t.right = delete(t.element, t.right);
	}

        return t;
    }


    public void printTree(){
        System.out.print("[ ");
	print(root);
        System.out.print("]");
        System.out.print('\n');
    }

    public void print(BinaryTreeNode x) {
	if (x != null) {
	    print(x.left);
            System.out.print(x.element);
            System.out.print(" ");
            print(x.right);
        }
    }
}

class BSTComplete {
    public static void main(String [] args) {
	BinarySearchTree myTree = new BinarySearchTree();
	BinarySearchTree anotherTree = new BinarySearchTree();
        int e;

        for (int i = 0; i < 10; i++) {
	    e = (int) (20 * Math.random());
            myTree.recInsert(e);
            anotherTree.insert(e);
            System.out.println(e);
	}

        for (int i = 0; i < 10; i ++) {
            e = (int) (20 * Math.random());
            System.out.println(e + " : " + myTree.search(e) + " , " + anotherTree.search(e));
	}

        myTree.printTree();
        anotherTree.printTree();

        for (int i = 0; i< 10; i++) {
            e = (int) (20 * Math.random());
            System.out.println("Deleting: " + e);
            myTree.delete(e);
            myTree.printTree();
	}
    }
}