#include <iostream>
#include <iostream>
typedef unsigned int uint;

struct nodoAB {
    uint elem ;
    nodoAB * izq , * der ;
};
typedef nodoAB * AB ;

//¿Cómo representaría al árbol vacío con dicha representación?
//con NULL

//V. función copiar: que recibe un árbol y retorna una copia limpia (que no comparte registros de memoria) del mismo.
AB copia (AB a){ 
    if (a == NULL){
        return NULL;
    }else{ 
        AB nuevo = new nodoAB; 
        nuevo->elem = a->elem; 
        nuevo->izq = copia(a->izq); 
        nuevo->der = copia(a->der); 
    return nuevo; 
    } 
    
}

//I. función consArbol: que retorna un árbol no vacío a partir de un natural y otros dos árboles.
//De esta forma el arbol resultado comparte memoria con izq y der, porque apunto a los lugares de memoria originales
/*AB consArbol(uint elem, AB izq, AB der){
    AB nuevo = new nodoAB;
    nuevo->elem=elem;
    nuevo->izq=izq;
    nuevo->der=der;
    return nuevo;
}*/

// Si quiero que no comparta memoria debo crear una copia de izq y der antes
AB consArbol(uint elem, AB izq, AB der){
    AB nuevo = new nodoAB;
    nuevo->elem=elem;
    nuevo->izq=copia(izq);
    nuevo->der=copia(der);
    return nuevo;
}

//II. función contarElems: que recibe un árbol y retorna la cantidad de elementos del mismo.
uint contarElems(AB a){
    if (a==NULL){ // no tiene elementos
        return 0;
    }else{
        return 1 + contarElems(a->izq) + contarElems(a->der); //sumamos uno por la raiz, luego la cantidad de elementos de la izquierda mas los de la derecha
    }
}

//III. función contarHojas: que recibe un árbol y retorna la cantidad de hojas (nodos cuyos ambos subárboles son vacíos) del mismo.
uint contarHojas(AB a){
    if (a==NULL){
        return 0;
    }else if (a->izq==NULL && a->der==NULL) {
        return 1;
    }else{
        return contarHojas(a->izq) + contarHojas(a->der); 
    } 
}

//IV. función altura: que recibe un árbol y retorna la altura del mismo. Si el árbol es vacío su altura es 0.
uint altura(AB a){
    if (a==NULL){
        return 0;
    }
    uint altizq=altura(a->izq);
    uint altder=altura(a->der);
    if (altizq>altder){
        return altizq+1;
    }else{
        return altder+1;
    }
}



//VI. procedimiento liberarArbol: que recibe un árbol y elimina del mismo todos los nodos, liberando la memoria asociada a cada uno de ellos.
void liberarArbol(AB &a){
    if (a!=NULL){
        liberarArbol(a->izq);
        liberarArbol(a->der);
        delete a;
        a=NULL;
    }
}

int main()
{
    AB arbol = consArbol(1,consArbol(2,consArbol(4, NULL, NULL),consArbol(5, NULL, NULL)),consArbol(3, NULL, NULL));

    printf("Cantidad de elementos: %d \n", contarElems(arbol));
    printf("Cantidad de hojas: %d \n", contarHojas(arbol));
    printf("Altura del árbol: %d \n", altura(arbol));

    liberarArbol(arbol);

    return 0;
}