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

typedef struct estruturaArvBin{
	int valor;
	struct estruturaArvBin *esq, *dir;
} tipoArvBin;

int ehFolha(tipoArvBin *arv){
	if(arv->esq != NULL || arv->dir != NULL)
		return 0;
	return 1;
}

tipoArvBin **buscaNo(tipoArvBin** arv, int valor){
	if((*arv) != NULL){
		if((*arv)->valor == valor)
			return arv;
		if(valor > (*arv)->valor)
			buscaNo(&(*arv)->dir, valor);
		else
			buscaNo(&(*arv)->esq, valor);
	}

}

int maiorValorArvore(tipoArvBin* arv){
	if(arv->dir == NULL)
		return ((arv)->valor);
	maiorValorArvore((arv)->dir);
}


void insereNo(tipoArvBin **arv, int valor){
	tipoArvBin *novoNo;
	novoNo = (tipoArvBin*) malloc (sizeof(tipoArvBin));
	novoNo->valor = valor;
	novoNo->esq = NULL;
	novoNo->dir = NULL;

	if(*arv == NULL){
		*arv = novoNo;
	}else{
		if(valor <= (*arv)->valor)
			insereNo(&(*arv)->esq, valor);
		else
			insereNo(&(*arv)->dir, valor);
	}
}

void removeNo(tipoArvBin **arv, int valor){
	tipoArvBin *aux;
	int maiorVal;

	if( arv != NULL){
		if((*arv)->valor == valor){
			if(ehFolha(*arv)){
				free(*arv);
				*arv = NULL;
			}else if((*arv)->dir == NULL && (*arv)->esq != NULL){
				aux = *arv;
				*arv = (*arv)->esq;
				free(aux);
			}else if((*arv)->dir != NULL && (*arv)->esq == NULL){
				aux = *arv;
				*arv = (*arv)->dir;
				free(aux);
			}else{
				maiorVal = maiorValorArvore((*arv)->esq);
				(*arv)->valor = maiorVal;
				removeNo(&(*arv)->esq, maiorVal);
			}
		}else{
			if(valor > (*arv)->valor)
				removeNo(&(*arv)->dir, valor);
			else
				removeNo(&(*arv)->esq, valor);
		}
	}
}

void imprimePreOrdem(tipoArvBin *arv){
	if(arv != NULL){
		printf("[%d] ", arv->valor);
		imprimePreOrdem(arv->esq);
		imprimePreOrdem(arv->dir);
	}

}

int main(int argc, char const *argv[]){
	tipoArvBin *arvore, *noTeste;
	arvore = NULL;

	insereNo(&arvore, 10);
	insereNo(&arvore, 9);
	insereNo(&arvore, 50);
	insereNo(&arvore, 20);
	insereNo(&arvore, 2);
	insereNo(&arvore, 3);
	insereNo(&arvore, 4);
	insereNo(&arvore, -1);
	imprimePreOrdem(arvore);
	printf("\n");
  removeNo(&arvore, 10);
	removeNo(&arvore, 3);
	removeNo(&arvore, 4);
	removeNo(&arvore, -1);
	removeNo(&arvore, 9);

	imprimePreOrdem(arvore);

	return 0;
}