#include <iostream>
#include <algorithm>

using namespace std;

template <typename T>
class Nodo {
public:
    Nodo(T nuevoValor) {
        valor = nuevoValor;
    }

    T valor;
    Nodo<T>* izquierdo = nullptr;
    Nodo<T>* derecho = nullptr;
};

template <typename T>
class Arbol {
public:
    Arbol(){}

    void setRaiz(Nodo<T>* nuevaRaiz) {
        raiz = nuevaRaiz;
    }

    Nodo<T>* nodoRaiz() {
        return raiz;
    }

    void imprimirInfijo() {
        imprimirInfijo(raiz);
    }

    void imprimirPrefijo() {
        imprimirPrefijo(raiz);
    }

    void imprimirPosfijo() {
        imprimirPosfijo(raiz);
    }

    int altura() {
        return altura(raiz);
    }

private:

    int altura(Nodo<T>* actual) {
        if(!actual) {
            return 0;
        }

        int alturaHijoIzquierdo = altura(actual->izquierdo);
        int alturaHijoDerecho = altura(actual->derecho);
        return std::max(alturaHijoIzquierdo, alturaHijoDerecho) + 1;
    }

    void imprimirInfijo(Nodo<T>* actual) {
        if(!actual) {
            return;
        }

        imprimirInfijo(actual->izquierdo);
        cout << actual->valor << endl;
        imprimirInfijo(actual->derecho);
    }

    void imprimirPrefijo(Nodo<T>* actual) {
        if(!actual) {
            return;
        }

        cout << actual->valor << endl;
        imprimirInfijo(actual->izquierdo);
        imprimirInfijo(actual->derecho);
    }

    void imprimirPosfijo(Nodo<T>* actual) {
        if(!actual) {
            return;
        }

        imprimirInfijo(actual->izquierdo);
        imprimirInfijo(actual->derecho);
        cout << actual->valor << endl;
    }

    Nodo<T>* raiz = nullptr;
};

int main()
{
    auto nodoRaiz = new Nodo<int>(10);
    nodoRaiz->izquierdo = new Nodo<int>(20);
    nodoRaiz->derecho = new Nodo<int>(30);
    nodoRaiz->izquierdo->izquierdo = new Nodo<int>(40);

    Arbol<int> arbol;
    arbol.setRaiz(nodoRaiz);
    arbol.imprimirInfijo();
    cout<< "altura:" << arbol.altura();

    return 0;
}