class Node {

    Object label;
    Node leftchild;
    Node rightchild;

    Node(Node left, Node right, Object l) {
	label = l;
        leftchild = left;
	rightchild = right;
    }

    Object getLabel() { return label; }
    Node getLeft() { return leftchild; }
    Node getRight() { return rightchild; }
    void setLeft(Node n) { leftchild = n; }
    void setRight(Node n) { rightchild = n; }
    void setLabel(Object l) { label = l; }
}



public abstract class BinaryTree {

    Node root;
    Node deletePosition;

///////////////////////////////////////////////////////////////////

    public abstract boolean smallerThan(Object obj1, Object obj2);
    public abstract boolean greaterThan(Object obj1, Object obj2);
    public abstract boolean isEqual(Object obj1, Object obj2);


    public void insert(Object label) {

        root = insert(root,label);

    }

    public boolean find(Object label) {

	return find(root,label);

    }

    public void delete(Object label) {

	root = delete(root,label);

    }
 
    public void printInOrder() {

	if ( root == null ) return;

        printInOrder(root);


    }

///////////////////////////////////////////////////////////////////


    void printInOrder(Node n) {

	if ( n == null )
	    return;
	else if ( n.getLeft() == null && n.getRight() == null )
	    System.out.println(n.getLabel());
        else {
	    printInOrder(n.getLeft());
            System.out.println(n.getLabel());
            printInOrder(n.getRight());
	}

    }


    Node insert(Node r, Object l) {

        if ( r == null )
            r = new Node(null,null,l);
        else if ( smallerThan(r.getLabel(),l) )
            r.setRight(insert(r.getRight(),l));
        else if ( greaterThan(r.getLabel(),l) )
            r.setLeft(insert(r.getLeft(),l));

	return r;

    }

    boolean find(Node r, Object l) {

	if ( r == null )
	    return false;
	else if ( isEqual(r.getLabel(),l) )
	    return true;
	else if ( smallerThan(r.getLabel(),l) )
            return find(r.getRight(),l);
       
       return find(r.getLeft(),l);

    }

    Node delete(Node r, Object l) {

	if ( r != null ) {

	    if ( smallerThan(r.getLabel(),l) )
		r.setRight(delete(r.getRight(),l));
            else if ( greaterThan(r.getLabel(),l) ) 
                r.setLeft(delete(r.getLeft(),l));
            else {
		deletePosition = r;
		if ( deletePosition.getRight() == null )
		    r = deletePosition.getLeft();
                else if ( deletePosition.getLeft() == null )
                    r = deletePosition.getRight();
		else deletePosition.setLeft(
                          deleteTwoChildren(deletePosition.getLeft()));
		deletePosition = null;
	    }

	}

	return r;

    }

    Node deleteTwoChildren(Node n) {

	if ( n.getRight() != null ) 
	    n.setRight(deleteTwoChildren(n.getRight()));
        else {
	    deletePosition.setLabel(n.getLabel());
	    deletePosition = n;
	    n = n.getLeft();
	}

	return n;

    }

}