#include <iostream>

using namespace std;

struct NodoArbol
{
    int info;
    NodoArbol *hi;
    NodoArbol *hd;
};
typedef NodoArbol *arbol;

void inserta(arbol &,int);
void preOrden(arbol);
void enOrden(arbol);
void postOrden(arbol);
arbol buscar(arbol,int);
int numNodos(arbol);
int elemDer(arbol);
arbol mayorElemRecur(arbol);
int mayorIterativo(arbol);
void camino(arbol,int);
int longitudCamino(arbol,int);
void diferencia(arbol);
int segundoElem(arbol);
int main()
{
    arbol abb = NULL;
    int n, i, x, val,val1;

    cout<<"Numero de elementos: ";
    cin>>n;

    for(i=1;i<=n;i++)
    {
        cout<<"Ingrese elemento: ";
        cin>>x;
        inserta(abb,x);
    }

    /*cout<<"\nPreOrden"<<endl;
    preOrden(abb);

    cout<<"\nEnOrden"<<endl;
    enOrden(abb);

    cout<<"\nPost-Orden"<<endl;
    postOrden(abb);

    cout<<"\nIngrese elemento a buscar: ";
    cin>>val;

    arbol p;
    p = buscar(abb,val);
    if(p!=NULL)
    {
        cout<<"El elemento se encuentra en el arbol"<<endl;
    }
    else
    {
        cout<<"El elemento no se encuentra en el arbol"<<endl;
    }

    cout<<"El numero de nodos es: "<<numNodos(abb)<<endl;
    cout<<"Elementos a la derecha del nodo.. :";
    cin>>val1;
    p = buscar(abb,val1);
    cout<<"Hay "<<elemDer(p)-1;

    p = mayorElemRecur(abb);
    if(p!=NULL)
    {
        cout<<"\nEl mayor elemento es: "<<p->info<<endl;
    }

    cout<<"EL mayor elemento iterativamente: "<<mayorIterativo(abb);

    cout<<"\nIngrese nodo para ver su camino: ";
    cin>>x;

    camino(abb,x);

    cout<<"\nEl camino recorrido es: "<<longitudCamino(abb,x);*/

    diferencia(abb);

    cout<<"El segundo elemento menor del arbol es: "<<segundoElem(abb);

}

void inserta(arbol &abb, int x)
{
    if(abb == NULL)
    {
        abb = new NodoArbol;
        abb->info = x;
        abb->hi = NULL;
        abb->hd = NULL;
    }
    else
    {
        if(x<abb->info)
        {
            inserta(abb->hi,x);
        }
        else
        {
            if(x>abb->info)
            {
                inserta(abb->hd,x);
            }
        }
    }
}

void preOrden(arbol abb)
{
    if(abb != NULL)
    {
        cout<<abb->info<<" ";
        preOrden(abb->hi);
        preOrden(abb->hd);
    }
}

void enOrden(arbol abb)
{
    if(abb != NULL)
    {
       enOrden(abb->hi);
       cout<<abb->info<<" ";
       enOrden(abb->hd);
    }
}
void postOrden(arbol abb)
{
    if(abb != NULL)
    {
        postOrden(abb->hi);
        postOrden(abb->hd);
        cout<<abb->info<<" ";
    }
}

arbol buscar(arbol abb,int x)
{
    if(abb != NULL)
    {
        if(abb->info == x)
        {
            return abb;
        }
        else
        {
            if(x < abb->info)
            {
                return buscar(abb->hi,x);
            }
            else
            {
                return buscar(abb->hd,x);
            }
        }
    }
    else
    {
        return NULL;
    }
}

int numNodos(arbol abb)
{
    if(abb!=NULL)
    {
        return 1+numNodos(abb->hi)+numNodos(abb->hd);
    }
    else
        return 0;
}
int elemDer(arbol abb)
{
    if(abb!=NULL)
    {
            return 1+elemDer(abb->hd);
    }
    else
    {
        return 0;
    }
}
arbol mayorElemRecur(arbol abb)
{
    if(abb != NULL)
    {
        if(abb->hd != NULL)
        {
            return mayorElemRecur(abb->hd);
        }
        else
        {
            return abb;
        }
    }
    else
    {
        return NULL;
    }
}
int mayorIterativo(arbol abb)
{
    arbol p = abb;
    while(p->hd != NULL)
        p = p->hd;
    return p->info;
}

void camino(arbol abb,int x)
{
    int num = buscar(abb,x)->info;

    while(abb!=NULL)
    {
        if(abb->info > num)
        {
            cout<<abb->info<<" "<<endl;
            abb = abb->hi;
        }
        else
        {
            cout<<abb->info<<" "<<endl;
            abb = abb->hd;
        }
    }
}

int longitudCamino(arbol abb, int x)
{
    int c = 0;
    int num = buscar(abb,x)->info;
    while(abb!=NULL)
    {
        if(abb->info > num)
        {
            c++;
            abb = abb->hi;
        }
        else
        {
            c++;
            abb = abb->hd;
        }
    }
    return c;
}

void diferencia(arbol abb)
{
    int dif = 0;
    arbol p,q;
    p = abb;
    q = abb;

    while(p->hd!=NULL)
    {
        p = p->hd;
    }
    cout<<"Mayor elemento: "<<p->info<<endl;
    while(q->hi!=NULL)
    {
        q = q->hi;
    }
    cout<<"Menor elemento: "<<q->info<<endl;
    dif = p->info-q->info;
    cout<<"Diferencia entre ambos: "<<dif<<endl;
}

int segundoElem(arbol abb)
{
    arbol p = abb;

    while(p->hi!=NULL)
    {
        if(p->hi > p->hd)
        {
            return p->info;
        }
        p = p->hi;
    }

}