class BinaererSuchbaum {

  private boolean leer;
  private int inhalt;
  private BinaererSuchbaum linkesKind;
  private BinaererSuchbaum rechtesKind;

  public BinaererSuchbaum() {
    leer = true;
  } 

  public BinaererSuchbaum(int wert) {
    leer = false;
    inhalt = wert;
    linkesKind = new BinaererSuchbaum();
    rechtesKind = new BinaererSuchbaum();
  }
  
  private int getInhalt() {return inhalt;}

  private BinaererSuchbaum getLinkesKind() {return linkesKind;}

  private BinaererSuchbaum getRechtesKind() {return rechtesKind;}

  public String toString() {
    String temp = "<";
    if (! istLeer()) {
      if (! linkesKind.istLeer())
        temp = temp + linkesKind.toString();
      temp = temp + ">";
      temp = temp + inhalt;
      temp = temp + "<";
      if (! rechtesKind.istLeer())
        temp = temp + rechtesKind.toString();
    }
    temp = temp + ">";
    return temp;
  }

  public void druckeBaum() {
    System.out.println(toString());
  }

  public boolean istLeer() {return leer;}

  public void fuegeEin(int wert) {
    if (istLeer()) {
       leer = false;
       inhalt = wert;
       linkesKind = new BinaererSuchbaum(); 
       rechtesKind = new BinaererSuchbaum();
    }
    else {
      if (wert < getInhalt()) {
	linkesKind.fuegeEin(wert);
      }
      else if (wert >= getInhalt()) {
	rechtesKind.fuegeEin(wert);
      }
    }
  }

  public int suche(int wert) {
    if (istLeer())
      return -1;
    else if (wert == inhalt)
      return inhalt;
    else if (wert < inhalt)
      return linkesKind.suche(wert);
    else
      return rechtesKind.suche(wert);
  }

  public int gibMinimum() {
    if (istLeer())
      return -1;
    else if (linkesKind.istLeer()) return inhalt;
    else return linkesKind.gibMinimum();
  }
  
  public int gibMaximum() {
    if (istLeer())
      return -1;
    else if (rechtesKind.istLeer()) return inhalt;
    else return rechtesKind.gibMaximum();
  }

  public void loescheInhalt(int wert) {
    if (istLeer())
      return;
    else if (wert < inhalt) {
      linkesKind.loescheInhalt(wert);
    }
    else if (wert > inhalt) {
      rechtesKind.loescheInhalt(wert);
    }
    else { // (wert == inhalt)
      if (! linkesKind.istLeer()) {
        if (! rechtesKind.istLeer()) { //Knoten hat zwei Kinder
          inhalt = linkesKind.gibMaximum();
          linkesKind.loescheInhalt(inhalt);
        }
        else { //Knoten hat nur linkes Kind
	  inhalt = linkesKind.getInhalt();
	  rechtesKind = linkesKind.getRechtesKind();
	  linkesKind = linkesKind.getLinkesKind();
        }
      }
      else if (! rechtesKind.istLeer()) { //Knoten hat nur rechtes Kind
	inhalt = rechtesKind.getInhalt();
	linkesKind = rechtesKind.getLinkesKind();
	rechtesKind = rechtesKind.getRechtesKind();
      }
      else { // Knoten ist Blatt
        leer = true;
        linkesKind = null;
        rechtesKind = null;
      }
    }
    return;
  }
    

}