//Esercizio 1.
  //**************ALTEZZA DI UN NODO (ricorsivo)************************
  protected int altezza(IntBSTNodo p) {
    if (p == null) return 0;            //albero vuoto? allora restituisci 0!
    int a = altezza(p.left);            //metti in a altezza ramo sx
    int b = altezza(p.right);           //metti in b altezza ramo dx
    if (a > b) return a + 1;            //restituisci ramo pių lungo (+1)
    else return b + 1;
  }
  //metodo sovraccaricato per l'altezza dell'albero
  public int altezza() {
    return altezza(root)-1;
  }

//Esercizio 2.
 //************NUMERO DI FOGLIE DI UN SOTTOALBERO (ricorsivo)*****************
  protected int foglie(IntBSTNodo p) {
    if (p == null) return 0;                               //albero vuoto? allora restituisci 0!
    else if (p.left==null && p.right==null) return 1;
         else return foglie(p.left) + foglie(p.right);
  }
  //metodo sovraccaricato per le foglie dell'albero
  public int foglie() {
    return foglie(root);
  }
  
//Esercizio 3.
   //Intersezione tra 2 alberi
  public static IntBST Intersezione(IntBST a, IntBST b) {
    if (!a.IsEmpty() && !b.IsEmpty()) {
      IntBST r = new IntBST();
      Lista la = a.inorder();
      int val;
      try {
        for (;;) {
          val = la.getNextElem();                       //prende elemento da lista a
          if (b.ricerca(val) != null) r.inserisci(val); //inserisci in b se presente
        }
      } catch (BottomOfListException e) {}
      return r;
    }
    return null;
  }
 
 //Esercizio 5.
   //Restituisce una Lista con i nodi ordinati per livello
  //(Attraversamento in ampiezza alto/basso, sinistra/destra)
  public Lista IterSxDxLevelVisit() {
    Lista l = new Lista();
    LLCodaObject c = new LLCodaObject();
    IntBSTNodo p = root;
    if (p == null) return null;
    c.EnQueque(p);
    while (!c.IsEmpty()) {
      p = (IntBSTNodo)c.DeQueque();
      l.InsertTail(p.key);
      if (p.left != null) c.EnQueque(p.left);
      if (p.right != null) c.EnQueque(p.right);
    }
    return l;
  }

//Esercizio 8.
  //************RESTITUZIONE DEL "FRATELLO" DI UN NODO*************************
  public IntBSTNodo fratello(IntBSTNodo p) {
    IntBSTNodo aux = root, prev = null;
    int val = p.key;
    while (aux != null) {
      if (p == aux) {                                   //chiave trovata
        if (prev != null) {                             //ha un padre
          if (prev.left == p) return prev.right;        //restituisce fratello
          else return prev.left;
        }
        else return null;                               //č la radice!
      }
      else {
        prev = aux;                                     
        if (val < aux.key) aux = aux.left;              //continua ricerca BST
        else aux = aux.right;                           
      }
    }
    return null;
  }

//Esercizio 9.
  public static Lista ListaDecrescente(IntBST Albero) {
    Lista l = new Lista();
    InverseinOrder(Albero.root, l);
    return l;
  }
  
  public static void InverseinOrder(IntBSTNodo p, Lista l) {
    if (p != null) {
      //Attraversamento RVL (ordinamento discendente)
      InverseinOrder(p.right, l);
      l.InsertTail(p.visit());
      InverseinOrder(p.left, l);
    }
  }

  
//Esercizio 10.  
  //Restituisce il valore del livello col numero maggiore dei nodi
  /*
  Liv   #Nodi     Coda "livello"                  Coda "figli"
  ----------------------------------------------------------------------
  0      1         | 15 |                       => | 20 | 7  |
  1      2         | 20 | 7 |                   => | 22 | 18 | 9  |  3 |
  2      4         | 22 | 18 | 9  |  3 |        => | 21 | 17 | 5  |
  3      3         | 21 | 17 | 5  |             => |null|
  */
   
  public int LevelWithMaxNode() {
    LLCodaObject livello = new LLCodaObject();
    IntBSTNodo p = root;
    int cntNodi=0, cntLiv=0, maxNodi=0, maxLiv=0;
    if (p == null) return -1;
    livello.EnQueque(p);
    while (!livello.IsEmpty()) {
      LLCodaObject figli = new LLCodaObject();
      while (!livello.IsEmpty()) {
        p = (IntBSTNodo)livello.DeQueque();
        if (p.right != null) figli.EnQueque(p.right);
        if (p.left != null) figli.EnQueque(p.left);
        cntNodi++;
      }
      if (cntNodi > maxNodi) {
        maxNodi = cntNodi;
        maxLiv = cntLiv;
      }
      cntLiv++;
      livello = figli;
      cntNodi = 0;
    }
    return maxLiv;    
  }