import java.io.*;

class PasDeSuccesseur extends Exception{
  PasDeSuccesseur(){}
  PasDeSuccesseur(int n){
    super(""+n);
  }
}

class NoeudAbsent extends Exception{
  NoeudAbsent(){}
  NoeudAbsent(int n){
    super(""+n);
  }
}

class ArbreVide extends Exception{}



class Arbre{
  private Noeud racine;

  private class Noeud{
    int cle;
    Noeud gauche;
    Noeud droit;

    Noeud(int i){cle=i;}
    Noeud(int i, Noeud gauche, Noeud droit){
      cle=i; 
      gauche=gauche; 
      droit=droit;
    }
  }

  Arbre(){}
  Arbre(Noeud e){racine=e;}
  Arbre(int i){racine= new Noeud(i);} 
  Arbre(int i, Arbre fg, Arbre fd){
    racine=new Noeud(i,fg.racine,fd.racine);
  }

  boolean estVide(){
    return (racine==null);
  }

  Arbre filsGauche(){ 
    return new Arbre(racine.gauche);
  }

  Arbre filsDroit(){
    return new Arbre(racine.droit);
  }

  /* La hauteur d'un arbre vide est -1*/

  int hauteur(){
    int h,hd,hg;
    
    if (estVide()) return -1;
    hd=filsDroit().hauteur();
    hg=filsGauche().hauteur();
    return (hd<hg)?hg+1:hd+1;
  }

  /*il serait peut-etre souhaitable de jeter une exception si 
    l'arbre est vide. 
    */

  int minimum(){
    if (filsGauche().estVide()) return racine.cle;
    else return filsGauche().minimum();
  }

  void ajouter(int m){
    Arbre a;

    if (estVide()) {
      racine = new Noeud (m);
    } else {
      if (m<racine.cle) {
	a=filsGauche();
	a.ajouter(m);
	racine.gauche=a.racine;
      } else { 
	if (m>racine.cle) {
	  a=filsDroit();
	  a.ajouter(m);
	  racine.droit=a.racine;
	}    
      }
    }
  }

  /* Recherche du successeur d'un noeud, on jete des exceptions si le noeud 
     n'existe pas ou si il n'a pas de successeurs
     */
    
    int rechercheSucc(int n, Arbre succ) throws NoeudAbsent, PasDeSuccesseur {
	// succ indique le dernier noeud pour lequel on est descendu
        // à gauche dans la chaîne des appels, et vaut null si ce noeud 
        // n'existe pas encore.

	if (estVide()) throw new NoeudAbsent(n);
	if (racine.cle > n) return filsGauche().rechercheSucc(n,this);
	if (racine.cle < n) return filsDroit().rechercheSucc(n,succ);
	
        // arrivé à ce point, this est non vide, et sa clef vaut n :
	if (filsDroit().estVide()) {
	    if (succ == null) throw new PasDeSuccesseur(n);
	    return succ.racine.cle;
	}
	return filsDroit().minimum();

    }

    // appel principal de rechercheSucc().
    int successeur(int n) throws NoeudAbsent, PasDeSuccesseur { 
	return rechercheSucc(n,null);
    }
    
 

  void affiche(String s, boolean b, boolean sommet){
    if (!estVide()) {
      filsDroit().affiche(s+((!b && !sommet)?"|\t":"\t"),true,false);
      System.out.println(s+racine.cle+" ----\t|");
      filsGauche().affiche(s+((b && !sommet)?"|\t":"\t"),false,false);
    }
  }

  /* Les deux methodes suivantes implementes une version amelioree de la methode affiche
     Le probleme des "queues" des feuilles est regle, et on equilibre l'arbre en prenant
     en compte la profondeur au moment d'afficher un noeud vide.
     Evidemment c'est plus complique que la methode affiche
     */

  void afficheAmeliore(String s, boolean b, boolean sommet, int profondeur){
    if (!estVide()) {
      filsDroit().afficheAmeliore(s+((!b && !sommet)?"|\t":"\t"),true,false,profondeur-1);
      if (!(filsGauche().estVide() && filsDroit().estVide())) System.out.println(s+racine.cle+" ----\t|");
      else System.out.println(s+racine.cle);
      filsGauche().afficheAmeliore(s+((b && !sommet)?"|\t":"\t"),false,false,profondeur-1);
    } else {
      for (int i=1; i<java.lang.Math.pow(2,profondeur+1);i++) System.out.println(s);
    }
  }

  void afficheArbre(){
    afficheAmeliore("",true,true,hauteur());
    // affiche("",true,true);
  }
      
}




class EssaiArbre{

  /*cette methode construit l'ABR complet pour les entiers entre i et j ce qui
    peut etre util pour faire des tests
    */
 
  static Arbre arbreComplet(int i,int j){
    Arbre a;
    int milieu;

    if (i==j) a=new Arbre(i);
    else {
      if (j<i) a=new Arbre();
      else {
	milieu=(i+j)/2;
	a=new Arbre(milieu,arbreComplet(i,milieu-1),arbreComplet(milieu+1,j));
      }
    }
    return a;
  }

  /* Cette methode permet de rentrer un ABR a la main */

  static Arbre getArbre(){
    Arbre a = new Arbre();
    int[] tab={8,12,14,4,6,2,17,5,7,21,17};
    
    for (int i=0;i<tab.length;i++) a.ajouter(tab[i]);
    return a;
  }

    
    
 
  public static void main(String argv[]){
    Arbre a;
    a = getArbre();
    System.out.println("Voici l'arbre :");
    a.afficheArbre();
    System.out.println("\n");
    try { 
      System.out.println("Le successeur de 21 est "+a.successeur(21));
    } catch (PasDeSuccesseur e) {
      System.out.println(e+" n'a pas de successeur");
    } catch (NoeudAbsent e) {
      System.out.println(e+" n'est pas un noeud de l'arbre");
    }
  }

}