#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int elemento;
    struct Node *dir;
    struct Node *esq;
};
typedef struct Node node;

node *aloca(int elemento)
{
    node *novo =(node*) malloc(sizeof(node));
    novo->dir = NULL;
    novo->esq = NULL;
    novo->elemento = elemento;

    return novo;

}
void inserir(node *estrutura, int elemento)
{
    if(elemento < estrutura->elemento)
    {
        if(estrutura->esq == NULL)
        {
            estrutura->esq = (aloca(elemento));
        }
        else
            inserir(estrutura->esq,elemento);
    }

    if(elemento > estrutura->elemento)
    {
        if(estrutura->dir == NULL)
        {
            estrutura->dir = aloca(elemento);
        }
        else
            inserir(estrutura->dir,elemento);
    }
}

void em_ordem(node *estrutura)
{
    if(estrutura == NULL ){
        return;
    }
    em_ordem(estrutura->esq);

    printf("%d ",estrutura->elemento);
    em_ordem(estrutura->dir);
}

void pre_ordem(node *estrutura)
{
    if(estrutura == NULL)
        return;
    printf("%d ",estrutura->elemento);
    pre_ordem(estrutura->esq);
    pre_ordem(estrutura->dir);
}

void pos_ordem(node *estrutura)
{
    if(estrutura == NULL)
        return;
    pos_ordem(estrutura->esq);
    pos_ordem(estrutura->dir);
    printf("%d ",estrutura->elemento);
}

node *buscar(node *estrutura, int elemento)
{
    if(estrutura == NULL || estrutura->elemento == elemento)
        return estrutura;
    if(estrutura->elemento > elemento)
        return buscar(estrutura->esq,elemento);
    else
        return buscar(estrutura->dir,elemento);
}

node *encontrar_substituto(node* p)
{
    node* aux = p;

    /* loop down to find the leftmost leaf */
    while (aux && aux->esq != NULL)
        aux = aux->esq;

    return aux;
}

node* remover(node* p, int x)
{
    // caso base
    if (p == NULL) return p;

    // If the key to be deleted is smaller than the root's key
    if (x < p->elemento)
        p->esq = remover(p->esq, x);

    // If the key to be deleted is greater than the root's key,
    // then it lies in right subtree
    else if (x > p->elemento)
        p->dir = remover(p->dir, x);

    // if key is same as root's key, then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (p->esq == NULL)
        {
            node *temp = p->dir;
            free(p);
            return temp;
        }
        else if (p->dir == NULL)
        {
            node *temp = p->esq;
            free(p);
            return temp;
        }

        // node with two children: Get the inorder successor (smallest
        // in the right subtree)
        node* temp = encontrar_substituto(p->dir);

        // Copy the inorder successor's content to this node
        p->elemento = temp->elemento;

        // Delete the inorder successor
        p->dir = remover(p->dir, temp->elemento);
    }
    return p;
}

int contar_nos(node *p)
{
    int cnt = 1;

    if(p == NULL)
        return 0;

    cnt += contar_nos(p->dir);
    cnt += contar_nos(p->esq);

    return cnt;

}

int main()
{
    node arvore;
    arvore.dir = NULL;
    arvore.esq = NULL;

    printf("Digite o elemento da raiz da arvore: ");
    scanf("%d",&arvore.elemento);

    inserir(&arvore,2);
    inserir(&arvore,1);
    inserir(&arvore,3);

    inserir(&arvore,6);
    inserir(&arvore,5);
    inserir(&arvore,7);

    printf("Em ordem: "); em_ordem(&arvore); printf("\n");


    printf("\nContar: %d",contar_nos(&arvore));

}