#include <iostream>

struct nodoLista {
uint elem ;
nodoLista * sig ;
};
typedef nodoLista * Lista ;

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

//enOrden: que recibe un árbol b y retorna una 
//lista con los elementos de b ordenados según la
//recorrida en orden de b.

Lista enOrden(AB b){
    if (b==NULL){
        return NULL;
    }else{
        //creo la lista inOrder del subarbol izquierdo 
        Lista lista_izq = enOrden(b->izq);
        //creo la lista inOrder del subarbol derecho 
        Lista lista_der = enOrden(b->der);
        //creo un nodo y le doy el valor de la raiz
        Lista nuevo = new nodoLista;
        nuevo->elem=b->elem;
        nuevo->sig=lista_der;
        
        //se recorre la lista para llegar al ultimo nodo y apuntarlo a la raiz
        Lista aux=lista_izq;
        if (aux!=NULL){
            while(aux->sig!=NULL){
                aux=aux->sig;
            }
            aux->sig=nuevo;
        }else{
            return nuevo;
        }
        return lista_izq;
    }
}

//Traidos del ej1 para probar la funcion
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; 
    } 
    
}

void liberarArbol(AB &a){
    if (a!=NULL){
        liberarArbol(a->izq);
        liberarArbol(a->der);
        delete a;
        a=NULL;
    }
}

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;
}

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

    Lista aux = listaOrdenada;
    while (aux != NULL) {
        printf("%d ", aux->elem);
        aux = aux->sig;
    }
    
    liberarArbol(arbol);

    return 0;
}