#include <iostream>

using namespace std;

template <typename T>
class Nodo {
public:
    T valor;
    Nodo<T>* izquierdo = nullptr;
    Nodo<T>* derecho = nullptr;
};

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

    void insertar(T valor) {
        if(!raiz) {
            raiz = new Nodo<T>;
            raiz->valor = valor;
            return;
        }

        insertarRecursivo(raiz, valor);
    }

    void sacar(T valor) {
    }

    bool buscar(T valor) {
        return buscarRecursivo(raiz, valor);
    }

private:

    bool buscarRecursivo(Nodo<T>* actual, T valor) {


        if(!actual) {
             cout << "buscando" << valor << "no encontrado" << endl;
            return false;
        }

         cout << "buscando" << valor << "en" << actual->valor << endl;

        if(actual->valor == valor) {
            return true;
        }

        if(valor < actual->valor) {
            return buscarRecursivo(actual->izquierdo, valor);
        } else {
            return buscarRecursivo(actual->derecho, valor);
        }
    }

    void insertarRecursivo(Nodo<T>* actual, T valor) {
        if(actual->valor == valor) {
            return;
        }

        if(valor < actual->valor) {
            if(!actual->izquierdo) {
                // de mi lado izquierdo pero no tengo hijo
                actual->izquierdo = new Nodo<T>;
                actual->izquierdo->valor = valor;
                return;
            } else {
                insertarRecursivo(actual->izquierdo, valor);
            }
        } else {
            if(!actual->derecho) {
                // de mi lado izquierdo pero no tengo hijo
                actual->derecho = new Nodo<T>;
                actual->derecho->valor = valor;
                return;
            } else {
                insertarRecursivo(actual->derecho, valor);
            }
        }
    }

    Nodo<T>* raiz = nullptr;
};

int main()
{
    ArbolBusquedaBinaria<int> arbol;
    cout << "insertando";
    arbol.insertar(50);
    arbol.insertar(20);
    arbol.insertar(70);
    arbol.insertar(60);
    arbol.insertar(80);
    arbol.insertar(10);
    arbol.insertar(30);
    arbol.insertar(20);

    cout << "buscando";
    arbol.buscar(50);
    cout << "<<<<";
    arbol.buscar(20);
    cout << "<<<<";
    arbol.buscar(200);
    return 0;
}