public class searchTree {
    searchTree() {
	root = null;
    }
    
    public node find(int k) { 
	return find(root, k);
    } //Abfrage in jedem Durchlauf
    
    private node find(node p, int x) {
	if (p == null)
	    return null; 
	else if (x < p.key) 
	    return find(p.left, x);
	else if (x > p.key)
	    return find(p.right, x);
	else
	    return p;
    }
    
    public void insert(int k) {
	root = insert(root, k);
    } 
    
    private node insert(node p, int k) {
	if (p == null)
	    return new node(k); 
	else if (k < p.key) 
	    p.left = insert(p.left,k);
	else if (k > p.key)
	    p.right = insert(p.right,k);
	// ist der Schluessel schon vorhanden, sind wir fertig 
	return p;
    }
    
    
    public void remove(int k) {
	root = remove(root,k);
    } 
    
    private node predOfSymSucc (node p) {
	if (p.right.left != null) {
	    p = p.right;
	    while (p.left.left != null)
		p = p.left;
	}
	return p;
    } 

    private node remove(node p, int k) {
	if (p == null) return p;
	if (k < p.key) 
	    p.left = remove(p.left, k);
	else if (k > p.key) 
	    p.right = remove(p.right, k);
	else {
	    if (p.left == null) 
		return p.right;
	    if (p.right == null)
		return p.left;
	    node q = predOfSymSucc(p);
	    if (q == p) {
		p.key = p.right.key;
		p.right = p.right.right;
	    }
	    else {
		p.key = q.left.key;
		q.left = q.left.right;
	    }         
	}
	return p;
    }

    public void inOrder(){
	this.inOrder(this.root);

    }
    private void inOrder(node p){
	if (p != null){
	    inOrder(p.left);
	    System.out.println(p.key);
	    inOrder(p.right);
	}

    }
    
    private node root;

}