public class BinTree {

  TreeElem root;

  public BinTree() {
    this.root = null;
  }

  public void insert(int value) {
    if (this.root == null) {
      this.root = new TreeElem(value);
    } else {
      this.root.insert(new TreeElem(value));
    }
  }

  public void remove(int value) {
    if (this.root != null) {
      this.root = this.root.remove(new TreeElem(value));
    }
  }

  public boolean isElement(int value) {
    if (this.root != null) {
      return this.root.isElement(new TreeElem(value));
    } else {
      return false;
    }
  }

  public void inOrderPrint() {
    System.out.println("*****");
    if (this.root != null) {
      this.root.inOrderPrint();
    }
    System.out.println("*****");
  }

  public static void main(String[] args) {

    BinTree tree = new BinTree();
    tree.insert(5);
    tree.insert(1);
    tree.insert(3);
    tree.insert(2);
    tree.insert(4);
    tree.insert(6);
    tree.inOrderPrint();
    tree.remove(1);
    tree.remove(5);
    tree.remove(6);
    tree.remove(4);
    tree.remove(3);
    tree.inOrderPrint();
  }
}

class TreeElem {

  int value;
  TreeElem left;
  TreeElem right;

  TreeElem(int value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  void insert(TreeElem elem) {
    if (elem.value == this.value) {
      // schon vorhanden
      return;
    } else if (elem.value < this.value) {
      if (this.left == null) 
        this.left = elem;
      else
        this.left.insert(elem);
    } else {
      if (this.right == null) 
        this.right = elem;
      else
        this.right.insert(elem);
    }
  }

  TreeElem remove(TreeElem elem) {
    if (elem.value == this.value) {
      if (this.left == null) {
        return this.right;
      } else if (this.right == null) {
        return this.left;
      } else {
        this.left = this.left.reorg(this);
      }
    } else if (elem.value < this.value) {
      if (this.left != null) 
        this.left = this.left.remove(elem);
    } else {
      if (this.right != null) 
        this.right = this.right.remove(elem);
    }
    return this;
  }

  boolean isElement(TreeElem elem) {
    if (elem.value == this.value) {
      return true;
    } else if (elem.value < this.value) {
      if (this.left == null) 
        return false;
      else
        return this.left.isElement(elem);
    } else {
      if (this.right == null) 
        return false;
      else
        return this.right.isElement(elem);
    }
  }

  void inOrderPrint() {
    if (this.left != null) 
      this.left.inOrderPrint();
    System.out.println(this.value + " ");
    if (this.right != null) 
      this.right.inOrderPrint();
  }

  TreeElem reorg(TreeElem remove_node) {
    if (this.right == null) {
      remove_node.value = this.value;
      return this.left;
    } else {
      this.right = this.right.reorg(remove_node);
      return this;
    }
  }

}