//   NODO
import java.util.ArrayList;

public class NodoABB {
	Integer info;
	public NodoABB izq;
	public NodoABB der;
	
	public NodoABB (int info){
		this.info = info;
		izq=der= null;
	}
	
	
	public void insertar(NodoABB nuevo){
		if (info > nuevo.info){
			if (izq == null)
				izq = nuevo;
			else
				izq.insertar(nuevo);
		}else{
			if (der == null)
				der = nuevo;
			else
				der.insertar(nuevo);
		}
	}
	
	
	public void eliminar(NodoABB padre, String izqDer, int info){
		if (this.info == info){
			if (esHoja()){
				if (izqDer == "izq"){	//vine por izquierda
					padre.izq = null;
				}else{
					padre.der = null;
				}
			}else{	// por hipotesis tengo derecha o izquieda
				if (izq != null ){	//tomo el maximo de la izquierda
					this.info = izq.maximo();
					izq.eliminar(this, "izq", this.info);
				}else{
					this.info = der.minimo();
					der.eliminar(this, "der", this.info);
				}
			}
		}else{	//iteracion
			if (info<this.info && izq != null )
				izq.eliminar(this,"izq", info);
			if (info>this.info && der != null)
				der.eliminar(this,"der", info);
		}
	}
	
	
	boolean pertenece(int dato){
		if (dato==this.info)
			return true;
		if(dato<info && izq!=null)
			return izq.pertenece(dato);
		if(dato>info && der!=null)
			return der.pertenece(dato);
		return false;
	}	
	
	
	int cantNodos(){
		int ret= 1;
		
		if (izq!=null)
			ret= ret + izq.cantNodos();
		if (der!=null)
			ret= ret + der.cantNodos();
		return ret;
	}	
	
	
	public int altura(){	//cota superior O(n^2)
		int altIzq = 0, altDer= 0;
		
		if(izq!=null)
			altIzq= izq.altura();
		if(der!=null)
			altIzq= der.altura();
		
		return 1 +  Math.max( altIzq, altDer );
	}	
	
	
	boolean balanceado(){	//O(log n)
		Integer altI= 0, altD= 0;
		
		if(izq!=null)
			altI= izq.altura();
		if(der!=null)
			altD= der.altura();
		
		boolean ret= true;
		
		ret = Math.abs(altI-altD) <=1;
	
		if (izq!=null)
			ret= ret && izq.balanceado();
		if (der!=null)
			ret= ret && der.balanceado();
		
		return ret;
	}
	
	
	public Integer balanceado2() {	//O(n)
		Integer altI= 0, altD= 0;
		
		if (izq!=null)
			altI= izq.balanceado2();
		if (der!=null)
			altD= der.balanceado2();
		
		if( altI < 0 || altD < 0 )
			return -1;
		if(Math.abs(altI- altD) >1)
			return -1;
		else
			return 1 + Math.max(altI, altD);
	}	
	
	
	public void imprimirPreOrden() {	// PREORDEN=	Actual + Pre(izq) + Pre(der)
		System.out.println(info + " ");
		
		if(izq!=null)
			izq.imprimirPreOrden();
		
		if(der!=null)
			der.imprimirPreOrden();
	}
	

	public void imprimirInOrden() {		//INORDEN=	In(izq) + Actual + In(der)
		if(izq!=null)
			izq.imprimirInOrden();
		
		System.out.println(info + " ");
		
		if(der!=null)
			der.imprimirInOrden();
	}

	
	public void toListPreOrden(ArrayList<Integer> lista) {	// PREORDEN=	Actual + Pre(izq) + Pre(der)
		lista.add(info);
		
		if(izq!=null)
			izq.toListInOrden(lista);
		
		if(der!=null)
			der.toListInOrden(lista);
	}

	
	public void toListInOrden(ArrayList<Integer> lista) {		//INORDEN=	In(izq) + Actual + In(der)
		if(izq!=null)
			izq.toListInOrden(lista);
		
		lista.add(info);
		
		if(der!=null)
			der.toListInOrden(lista);
	}
	
	
	public void clonarArbol(ABB nuevoArbol) {	
		
		if(izq!=null)
			izq.clonarArbol(nuevoArbol);
		
		nuevoArbol.insertar(info);
		
		if(der!=null)
			der.clonarArbol(nuevoArbol);
	}	
	
	
	public String toString(){	// inOrder
		String ret ="";
		if (izq != null) ret = ret + izq.toString();
			ret =ret + info + " ";
		if (der != null) ret = ret + der.toString();
			return ret;
	}	
	
	
	public NodoABB buscar (NodoABB raíz, int dato){
		NodoABB actual = raíz;
		while (actual.info != dato) {
			if (dato < actual.info)
				actual = actual.izq;
			else
				actual = actual.der;
			if (actual == null)
				return null;
		}
		return actual;
	}
	

	private Integer minimo() {
		int min;
		if(this.izq==null)
			min= this.info;
		else
			min= this.izq.minimo();
		return min;
	}
	

	private Integer maximo() {
		int max;
		if(this.der==null)
			max= this.info;
		else
			max= this.der.maximo();
		return max;
	}
	

	public boolean esHoja(){
		return (izq == null) && (der == null);
	}
	
}
//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
//   ABB
import java.util.ArrayList;
import java.util.List;

public class ABB {
	public NodoABB raiz;
	//No tenemos constructor!
	
	public void insertar(int info){
		NodoABB nuevo = new NodoABB(info);
		if (raiz == null){
			raiz = nuevo;
		}else{
			raiz.insertar(nuevo);
		}
	}

	
	public void eliminar(int info){
		if (raiz != null){		//caso base1
			if (raiz.info == info && raiz.esHoja()){	//caso base2
				raiz = null;
			}else{
				raiz.eliminar(null,null, info);	// (el raiz no tiene padre)
			}
		}
	}
	
	
	boolean pertenece(int dato){
		if (raiz==null)
			return false;
		else return raiz.pertenece(dato);
	}
	
	
	int cantNodos(){
		int ret= 0;
		if(raiz!=null)
			ret= raiz.cantNodos();
		return ret;
	}
	
	
	int altura(){
		if(raiz!=null)
			return raiz.altura();
		return 0;			
	}
	
	
	boolean balanceado(){
		if(raiz==null)
			return true;
		else 
			return raiz.balanceado();
	}
	
	
	boolean balanceado2(){
		if(raiz==null)
			return true;
		else 
			return raiz.balanceado2() >-1;
	}
	
	
	public void imprimirPreOrden(){
		if(raiz==null)
			System.out.println("<Arbol vacio>");
		else
			raiz.imprimirPreOrden();
	}
	
	
	public void imprimirInOrden(){
		if(raiz==null)
			System.out.println("<Arbol vacio>");
		else
			raiz.imprimirInOrden();
	}
	
	
	public ArrayList<Integer> toListPreOrden() {	//PREORDEN=	Actual + Pre(izq) + Pre(der)
		ArrayList<Integer> lista= new ArrayList<Integer>();
		if(raiz!=null)
			raiz.toListPreOrden(lista);
		return lista;
	}
	
	
	public ArrayList<Integer> toListInOrden() {
		ArrayList<Integer> lista= new ArrayList<Integer>();
		if(raiz!=null)
			raiz.toListInOrden(lista);
		return lista;
	}
	
	
	public ABB clonarArbol(){
        ABB nuevoArbol= new ABB();
        if( raiz!=null ){
        	raiz.clonarArbol(nuevoArbol);
        }
        return nuevoArbol;
    }
	
	
	public String toString(){
		String ret= " ";
		if (raiz!=null)
				ret= raiz.toString();
		return ret;
	}
}
//^&^&^&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
//   MAIN
package clase4b;

public class Main {

	public static void main(String[] args) {
		ABB a= new ABB();
		ABB b= new ABB();
		
		
		a.insertar(8);
		a.insertar(5);
		a.insertar(6);
		a.insertar(4);
		a.insertar(10);
		a.insertar(9);
		a.insertar(11);
		
		b= a.clonarArbol();
		
		b.eliminar(6);
		a.eliminar(9);
		
		System.out.println("Arbol a: " + a.toString());
		System.out.println("Arbol b: " + b.toString());
		
		System.out.println( "cantidad de nodos en a: " + a.cantNodos() );
		System.out.println( "altura en b: " + b.altura() );
		System.out.println( "a esta balanceado? " + a.balanceado() );
		
		System.out.println("Pertenece? " + a.pertenece(6));

	}

}