class TNode{
    int id;
    String data;
    TNode left, right;

    TNode(int i, String d){
	id=i;
	data=d;
	left=right=null;
    } // Konstruktor

    public String toString(){
	return id + ": " + data;
    } // toString
} // TNode

class TreeException extends RuntimeException{
    public TreeException(String msg){
	super(msg);
    }
}

class BinSearchTree {
    private TNode root=null;

    public TNode retrive(int sought){
	return retriveNode(root, sought);
    }

    private TNode retriveNode(TNode node, int sought){
	if (node == null)
	    return null;
	else if (node.id == sought)
	    return node;
	else if (node.id > sought)
	    return retriveNode(node.left, sought);
	else
	    return retriveNode(node.right, sought);
    } // retriveNode


    public void insert(int id, String data){
	TNode newNode = new TNode(id, data);
	root=insertNode(root, newNode);
    }

    private TNode insertNode(TNode node, TNode newNode){
	if (node == null)
	    node = newNode;
	else if (node.id > newNode.id)
	    node.left = insertNode(node.left, newNode);
	else
	    node.right = insertNode(node.right, newNode);
	return node;
    }

    public void print(){
	printTree(root);
    }

    private void printTree(TNode node){
	if (node != null){
	    printTree(node.left);
	    System.out.println(node);
	    printTree(node.right);
	}
    }

    public void print2(){
	printTree2(root, 1);
    }

    private void printTree2(TNode node, int depth) {
	if (node != null){
	    printTree2(node.left, depth+1);
	    for(int i=0; i<depth; i++) System.out.print("  ");
	    System.out.println(node);
	    printTree2(node.right, depth+1);
	}
    }

    public void delete(int sought) throws TreeException {
	root = deleteNode(root, sought);
    }

    private TNode findLeftmost(TNode node){
	if (node.left == null)
	    return node;
	else
	    return findLeftmost(node.left);
    }

    private TNode deleteLeftmost(TNode node){
	if (node.left == null)
	    return node.right;
	else {
	    node.left = deleteLeftmost(node.left);
	    return node;
	}
    }
	    
    private TNode deleteNode(TNode node, int sought) throws TreeException{
	if (node == null)
	    throw new TreeException("No such element!");
	else if (node.id > sought)
	    node.left = deleteNode(node.left, sought);
	else if (node.id < sought)
	    node.right = deleteNode(node.right, sought);
	else if (node.left == null)
	    node = node.right;
	else if (node.right == null)
	    node = node.left;
	else {
	    TNode tmp=findLeftmost(node.right);
	    node.id = tmp.id;
	    node.data = tmp.data;
	    node.right = deleteLeftmost(node.right);
	}
	return node;
    }
}