#include <iostream>

#include <stdio.h>

typedef unsigned int uint;

struct nodoABB {
    uint elem;
    nodoABB* izq;
    nodoABB* der;
};
typedef nodoABB* ABB;

void insertar(ABB& santi, uint x) {
    if (santi == NULL) {
        ABB nuevo = new nodoABB;
        nuevo->elem = x;
        nuevo->izq = NULL;
        nuevo->der = NULL;
        santi = nuevo;
    } else if (x > santi->elem) {
        insertar(santi->der, x);
    } else if (x < santi->elem) {
        insertar(santi->izq, x);
    }
}

/* Busca el k-esimo en b.
Devuelve en 'cantidad ' la cantidad de elementos de 'b'
que se visitó. Si " cantidad >= k" , devuelve el k-esimo en 'res '. */

void kesimoAux(uint k, ABB b, uint& cantidad, ABB& res) {
/* Si el árbol está vacio entonces la cantidad de elementos recorrida es cero y
no se asigna valor a res porque no se llega al k-esimo*/
    if (b == NULL) {
        cantidad = 0;
    } else {
// Primero llamo al subarbol izquierdo porque recorro de izquierda a derecha
        kesimoAux(k, b->izq, cantidad, res);
/*
Al salir del subarbol izquierdo tengo tres posibilidades:
1 - que el siguiente elemento sea el k-esimo
2 - que el k-esimo , si existe , se encuentre en
el subarbol derecho
3 - o que ya lo haya encontrado en la recorrida
en el subarbol izquierdo .
*/

/*
Caso 1: El elemento en el que me encuentro situado es el k-esimo del arbol
*/
        if (cantidad == k - 1) {
            cantidad++;
            res = b;
/*
Caso 2: hay que continuar la búsqueda en el subarbol derecho
*/
        } else if (cantidad < k - 1) {
            cantidad++;  // Se incluye la raíz en los visitados
            uint cant_der;
            kesimoAux(k - cantidad, b->der, cant_der, res);
            // Actualizo cantidad con ambas partes del árbol
            cantidad += cant_der;
        
/*
Caso 3: ya haber encontrado el elemento en el subarbol ←-
izquierdo .
*/
        } else {
/*
No es necesario asignar valor a res porque ya se asigno a la salida de la llamada recursiva .
Lo único que hay que hacer es actualizar el valor de cantidad , recordando que esta variable es el contador de
elementos del árbol que se recorrieron.
*/
            cantidad++;
        }
    }
}

ABB kesimo(uint k, ABB b) {
    ABB res = NULL;
    uint cantidad;
    kesimoAux(k, b, cantidad, res);
    return res;
}

//Traidos del ej1 para probar la funcion
ABB copia (ABB a){ 
    if (a == NULL){
        return NULL;
    }else{ 
        ABB nuevo = new nodoABB; 
        nuevo->elem = a->elem; 
        nuevo->izq = copia(a->izq); 
        nuevo->der = copia(a->der); 
    return nuevo; 
    } 
    
}

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

ABB consArbol(uint elem, ABB izq, ABB der){
    ABB nuevo = new nodoABB;
    nuevo->elem=elem;
    nuevo->izq=copia(izq);
    nuevo->der=copia(der);
    return nuevo;
}

int main() {
    ABB arbol = consArbol(8,consArbol(2,consArbol(1, NULL, NULL),consArbol(5, NULL, NULL)),consArbol(9, NULL, NULL));
    
    insertar(arbol, 4);
    
    int k = 6;

    ABB k_esimo = kesimo(k, arbol);

    if (k_esimo != NULL) {
        printf("El %d-ésimo elemento es: %d\n", k, k_esimo->elem);
    } else {
        printf("No existe un %d-ésimo elemento en el árbol.\n", k);
    }

    liberarArbol(arbol);

    return 0;
}