/*
    Scrivere un metedo statico Java che, date due chiavi e un albero binario di ricerca,
    restituisca il nodo antenato più vicino ai nodi con le chiavi fornite.
    Nota: (le chiavi possono non essere presenti nell'albero)
    
      public static IntNodoBST LCA (IntBST A, int N, int M)
*/

public class Esame__23_09_2002 {
  public static void main(String[] args) {
    BST tree = new BST();
    int Dati[] = {10,5,3,1,2,4,7,8,9,6,15,13,12,11,14,17,18,19,16};
    for (int i=0; i<Dati.length; i++) tree.insert(new Integer(Dati[i]));
    tree.print();
    int n1 = 11, n2 = 19; //numeri di prova
    try {
      System.out.println("Per " + n1 + " e " + n2 + " il nodo antenato è: " +
            LCA(tree, new Integer(n1), new Integer(n2)).getInfo());
    } catch (NullPointerException e) {
      System.out.println("Ameno una delle chiavi non è presente nell'albero!");
    }
        
  }
  

  public static BSTNode LCA (BST a, Object n, Object m) {
    BSTNode p, q, prev = null;
    p = q = a.getRoot();
    if (p == null) return null;
    while (p == q) {
      prev = p;
      if (((Comparable)p.getInfo()).compareTo(n) < 0) p = p.getRight();
      else if (((Comparable)p.getInfo()).compareTo(n) > 0) p = p.getLeft();
        
      if (((Comparable)q.getInfo()).compareTo(m) < 0) q = q.getRight();
      else if (((Comparable)q.getInfo()).compareTo(m) > 0) q = q.getLeft();
    }
    //determina se esistono le chiavi
    while (p != null && ((Comparable)p.getInfo()).compareTo(n) != 0)
      if (((Comparable)p.getInfo()).compareTo(n) < 0) p = p.getRight();
      else p = p.getLeft();
    while (q != null && ((Comparable)q.getInfo()).compareTo(m) != 0)
      if (((Comparable)q.getInfo()).compareTo(m) < 0) q = q.getRight();
      else q = q.getLeft();
    //Restituisce nodo antenato se le chiavi esistono
    if (p != null && q != null) return prev;
    else return null;
  }
}

//*******LE (SOLITE) CLASSI ACCESSORIE***************
//classe BST
class BST {
  private BSTNode root;
  //buider
  public BST() {
    root = null;
  }
  public BST(Object o) {
    root = new BSTNode(o);
  }
  //public method
  public boolean isEmpty() {
    return (root == null);
  }
  public BSTNode getRoot() {
    return root;
  }
  public boolean insert(Object o) {
    if (isEmpty())
      root = new BSTNode(o);
    else {
      BSTNode p = root, prev = null;
      while (p != null) {
        if (((Comparable)p.getInfo()).compareTo(o) == 0)
          return false;
        prev = p;
        if (((Comparable)p.getInfo()).compareTo(o) < 0)
          p = p.getRight();
        else
          p = p.getLeft();
      }
      //Qui aux == null e prev è una foglia
      if (((Comparable)prev.getInfo()).compareTo(o) < 0)
        prev.setRight(new BSTNode(o));
      else
        prev.setLeft(new BSTNode(o));
    }
    return true;
  }
  public void print() {
    print(root, 0);
  }
  private void print(BSTNode p, int level) {
    if (p  != null) {
      print(p.getRight(), level + 1);
      for (int k = 0; k < level; k++) System.out.print("\t\t");
      System.out.println(p.getInfo());
      print(p.getLeft(), level + 1);
    }
  }

}


//classe Nodo per BST
class BSTNode {
  private Object info;
  private BSTNode left, right;
  //buider
  public BSTNode(Object o) {
    this(o, null, null);
  }
  public BSTNode(Object o, BSTNode l, BSTNode r) {
    info = o;
    left = l;
    right = r;
  }
  //public method
  public Object getInfo() {
    return info;
  }
  public void setInfo(Object o) {
    info = o;
  }
  public BSTNode getLeft() {
    return left;
  }
  public BSTNode getRight() {
    return right;
  }
  public void setLeft(BSTNode l) {
    left = l;
  }
  public void setRight(BSTNode r) {
    right = r;
  }
}