#include <iostream>
#include <vector>
#include <memory>

//-----------------------------------------------------------------------------
// Estrutura para representar um no' da arvore
// Guarda o valor e ponteiros para raizes das sub-arvores da esquerda e direita.
// Responsavel pelo gerenciamento das sub-arvores (por isso unique_ptr).
struct Noh {
    int valor;
    std::unique_ptr<Noh> esquerda, direita;
};

//-----------------------------------------------------------------------------
// Funcoes para lidar com arvores de busca binaria.
//

// Insere um no' com valor dado na (sub-)arvore com a raiz especificada.
// Se um no' com esse valor ja' existe, um novo nao e' inserido.
// Retorna ponteiro para o no' com o valor especificado.
Noh *insere(std::unique_ptr<Noh> &raiz, int valor);

// Busca um no' com o valor dado na (sub-)arvore com a raiz dada.
// Retorna ponteiro para o no'. Se nao encontra o valor, retorna nullptr.
Noh *busca(Noh *raiz, int valor);

// Retorna os elementos da arvore com a raiz dada armazenados em um vetor
// em ordem cresente.
std::vector<int> elementos_ordenados(Noh *raiz);

// Remove da (sub-)arvore com a raiz especificada um no com o valor dado,
// se existir. Se não existe, nada acontece.
void remove(std::unique_ptr<Noh> &raiz, int valor);

//-----------------------------------------------------------------------------
// Programa com alguns testes de operacoes em arvore de busca binaria.
int main(int , char *[])
{
    std::unique_ptr<Noh> arvore; // Arvore vazia (ponteiro e' inicializado nulo)

    // Valores a inserir na arvore (inicialmente)
    std::vector<int> valores{5, 3, 4, 1, 2, 7, 6, 0, 8};

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

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

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

    // Retira alguns valores
    remove(arvore, 4);
    remove(arvore, 3);
    remove(arvore, 11); // Este nao existia.
    remove(arvore, 8);
    remove(arvore, 5);

    // Verifica que elementos sobraram (em ordem)
    auto elementos = elementos_ordenados(arvore.get());
    std::cout << "Elementos: ";
    for (auto elem: elementos) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Fim do programa, nenhuma liberacao necessaria (ocorre automaticamente)
    return 0;
}


//-----------------------------------------------------------------------------
// Implementacoes das funcoes para lidar com arvores de busca binaria
//

// Insercao de um valor
Noh *insere(std::unique_ptr<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.get();
        }
    }
    else {
        auto novo = std::make_unique<Noh>();
        novo->valor = valor;
        raiz = std::move(novo);
        return raiz.get();
    }
}


// Busca de um valor
Noh *busca(Noh *raiz, int valor)
{
    if (raiz) {
        if (valor < raiz->valor) {
            return busca(raiz->esquerda.get(), valor);
        }
        else if (valor > raiz->valor) {
            return busca(raiz->direita.get(), valor);
        }
        else {
            return raiz;
        }

    }
    else {
        return nullptr;
    }
}


// Funcao auxiliar para retornar os valores ordenados.
// Coloca todos os elementos da (sub-)arvore com a raiz indicada em ordem
// no vertor existente elementos.
void elementos_ordenados_rec(std::vector<int> &elementos, Noh *raiz);

// Todos os valores em ordem crescente.
std::vector<int> elementos_ordenados(Noh *raiz)
{
    std::vector<int> todos;
    elementos_ordenados_rec(todos, raiz);
    return todos;
}


// Implemetacao da funcao axiliar para valores ordenados.
void elementos_ordenados_rec(std::vector<int> &elementos, Noh *raiz)
{
    if (raiz) {
        elementos_ordenados_rec(elementos, raiz->esquerda.get());
        elementos.push_back(raiz->valor);
        elementos_ordenados_rec(elementos, raiz->direita.get());
    }
}


// Funcoes auxiliares para remocao de um valor.
// Retorna menor valor da (sub-)arvore indicada por raiz.
int menor_valor (Noh *raiz);

// Retorna maior valor da (sub-)arvore indicada por raiz.
int maior_valor (Noh *raiz);

void remove(std::unique_ptr<Noh> &raiz, int valor)
{
    if (raiz) {
        if (valor < raiz->valor) {
            remove(raiz->esquerda, valor);
        }
        else if (valor > raiz->valor) {
            remove(raiz->direita, valor);
        }
        else {
            if (!raiz->esquerda  && !raiz->direita ) {
                raiz.reset(nullptr); // Libera espaco usado pelo ponteiro
                                     // e coloca em nullptr
            }
            else if (!raiz->direita) {
                int novo = maior_valor(raiz->esquerda.get());
                raiz->valor = novo;
                remove(raiz->esquerda, novo);
            }
            else {
                int novo = menor_valor(raiz->direita.get());
                raiz->valor = novo;
                remove(raiz->direita, novo);            }
        }
    }
}


// Implementacoes das funcoes auxiliares para remocao de valor.

// Menor valor
int menor_valor (Noh *raiz)
{
    if (raiz->esquerda) {
        return menor_valor(raiz->esquerda.get());
    }
    else {
        return raiz->valor;
    }
}

// Maior valor
int maior_valor (Noh *raiz)
{
    if (raiz->direita) {
        return maior_valor(raiz->direita.get());
    }
    else {
        return raiz->valor;
    }

}