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

typedef struct cel cel;

struct cel{
  int dado;
  cel *esq;
  cel *dir;
};

cel * cria_celula(int dado){
  cel * novo = (cel *) malloc(sizeof(cel));
  novo->dado = dado;
  novo->esq = NULL;
  novo->dir = NULL;
  return novo;
}

void imprime_inorder(cel * arvore){
  if(arvore == NULL) return;
  imprime_inorder(arvore->esq);
  printf("%d ", arvore->dado);
  imprime_inorder(arvore->dir);
}

void imprime_preorder(cel * arvore){
  if(arvore == NULL) return;
  printf("%d ", arvore->dado);
  imprime_preorder(arvore->esq);
  imprime_preorder(arvore->dir);
}

int calcula_altura(cel * arvore){
  if(arvore == NULL) return 0;
  int altura_esq = calcula_altura(arvore->esq);
  int altura_dir = calcula_altura(arvore->dir);
  if(altura_esq > altura_dir) return altura_esq + 1;
  else return altura_dir + 1;
}

//Devolve o endereço da celula com o valor, ou NULL
cel * busca_valor(cel * arvore, int valor){
  if(arvore == NULL) return NULL;
  if(arvore->dado == valor) return arvore;
  if(arvore->dado > valor) return busca_valor(arvore->esq, valor);
  else return busca_valor(arvore->dir, valor);
}


//insere valor na arvore e devolve o endereco da nova arvore com o valor
cel * insere_arvore(cel * arvore, int valor){
  if(arvore == NULL){
    return cria_celula(valor);
  }
  if(arvore->dado > valor){
    arvore->esq = insere_arvore(arvore->esq, valor);
  }else{
    arvore->dir = insere_arvore(arvore->dir, valor);
  }
  return arvore;
}

int main(){
  cel* arvore = NULL;
  arvore = insere_arvore(arvore, 10);
  arvore = insere_arvore(arvore, 5);
  arvore = insere_arvore(arvore, 7);
  arvore = insere_arvore(arvore, 6);
  arvore = insere_arvore(arvore, 11);
  
  imprime_inorder(arvore);
  printf("\n");
 
 
  printf("altura = %d\n", calcula_altura(arvore));
  
  cel * busca = busca_valor(arvore, 7);
  if(busca == NULL){
    printf("7 nao esta na arvore\n");
  }else{
    printf("7 esta na arvore\n");
  }
  
  busca = busca_valor(arvore, 12);
  if(busca == NULL){
    printf("12 nao esta na arvore\n");
  }else{
    printf("12 esta na arvore\n");
  }
  
  
  return 0;
}