#include <iostream>
#include <vector>

struct Noh {
    int valor;
    Noh *esquerda, *direita;
};

Noh *insere(Noh *&raiz, int valor)
{
    if (raiz) {
        if (valor < raiz->valor) {
            return insere(raiz->esquerda, valor);
        }
        else if (valor > raiz->valor) {
            return insere(raiz->direita, valor);
        }
        else {
            return raiz;
        }
    }
    else {
        Noh *novo = new Noh;
        novo->direita = novo->esquerda = nullptr;
        novo->valor = valor;
        raiz = novo;
        return novo;
    }
}

Noh *busca(Noh *raiz, int valor)
{
    if (raiz) {
        if (valor < raiz->valor) {
            return busca(raiz->esquerda, valor);
        }
        else if (valor > raiz->valor) {
            return busca(raiz->direita, valor);
        }
        else {
            return raiz;
        }
        
    }
    else {
        return nullptr;
    }
}

std::vector<int> elementos_ordenados_v0(Noh *raiz)
{
    if (raiz) {
        std::vector<int> da_esquerda = elementos_ordenados_v0(raiz->esquerda);
        std::vector<int> da_direita = elementos_ordenados_v0(raiz->direita);
        std::vector<int> todos(da_esquerda.size()+ da_direita.size()+1);
        int i = 0;
        for (auto elem: da_esquerda) {
            todos[i] = elem;
            ++i;
        }
        todos[i] = raiz->valor;
        ++i;
        for (auto elem: da_direita) {
            todos[i] = elem;
            ++i;
        }
        return todos;
    }
    else {
        return std::vector<int>();
    }
}

void elementos_ordenados_rec(std::vector<int> &elementos, Noh *raiz);

std::vector<int> elementos_ordenados(Noh *raiz)
{
    std::vector<int> todos;
    elementos_ordenados_rec(todos, raiz);
    return todos;
}

void elementos_ordenados_rec(std::vector<int> &elementos, Noh *raiz)
{
    if (raiz) {
        elementos_ordenados_rec(elementos, raiz->esquerda);
        elementos.push_back(raiz->valor);
        elementos_ordenados_rec(elementos, raiz->direita);
    }
}

int main(int , char *[])
{
    Noh *arvore{nullptr};
    std::vector<int> valores{5, 3, 4, 1, 2, 7, 6, 0, 8};

    for (auto valor: valores) {
        insere(arvore, valor);
    }

    auto existe = busca(arvore, 2);
    if (existe) {
        std::cout << "Achei um 2: " << existe->valor << std::endl;
    }
    else {
        std::cout << "Nao achei\n";
    }
    
    existe = busca(arvore, 11);
    if (existe) {
        std::cout << "Achei um 11: " << existe->valor << std::endl;
    }
    else {
        std::cout << "Nao achei\n";
    }

    auto elementos = elementos_ordenados(arvore);
    std::cout << "Elementos: ";
    for (auto elem: elementos) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    
    return 0;
}