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

typedef struct _Node {
	int key;
	int value;
	struct _Node* L;
	struct _Node* R;
} Node;

typedef struct {
	int count;
	Node *root;
} Tree;

Node* Add(Tree* T, int K) {
	Node** N = &(T->root);
	while (*N != NULL) {
		if ((*N)->key == K) return *N;
		if ((*N)->key < K) N = &((*N)->L);
		else N = &((*N)->R);
	}
	if ( (*N = malloc(sizeof(Node))) == NULL) return NULL;
	(*N)->key = K;
	(*N)->value = 0;
	(*N)->L = (*N)->R = NULL;
	T->count++;
	return *N;
}

Node** FindD(Tree* T, int K) {
	Node** FindDNode(Node** N, int K) {
		if (*N == NULL) return NULL;
		if ((*N)->key == K) return N;
		if ((*N)->key < K) return FindDNode(&((*N)->L), K);
		return FindDNode(&((*N)->R), K);
	}
	if (T == NULL) return NULL;
	return FindDNode(&(T->root), K);
}

Node* Find(Tree* T, int K) {
	Node* FindNode(Node* N, int K) {
		if (N == NULL) return NULL;
		if (N->key == K) return N;
		if (N->key < K) return FindNode(N->L, K);
		return FindNode(N->R, K);
	}
	if (T == NULL) return NULL;
	return FindNode(T->root, K);
}

Node* Insert(Tree* T, int K, int V) {
	Node* N = Find(T, K);
	if (N == NULL) return NULL;
	N->value = V;
	return N;
}

void Remove(Tree* T, int K) {
	Node** N = FindD(T, K);
	if (N == NULL) return;
	if (((**N).L == NULL) && ((**N).R == NULL)) {
		free(*N);
		*N = NULL;
		T->count--;
		return;
	}
	if (((**N).L != NULL) && ((**N).R == NULL)) {
		Node* Temp = *N;
		*N = (**N).L;
		free(Temp);
		T->count--;
		return;
	}
	if (((**N).L == NULL) && ((**N).R != NULL)) {
		Node* Temp = *N;
		*N = (**N).R;
		free(Temp);
		T->count--;
		return;
	}
	Node** GetSuccessor(Node** P) {
		if ((**P).L == NULL) return P;
		return GetSuccessor(&((**P).L));
	}
	Node** S = GetSuccessor(&((**N).R));
	(**S).L = (**N).L;
	(**S).R = (**N).R;
	free(*N);
	*N = malloc( sizeof(Node) );
	(*N)->key = (**S).key;
	(*N)->value = (**S).value;
	(*N)->L = (**S).L,
	(*N)->R = (**S).R;
	free(*S);
	*S = NULL;
	T->count--;
	return;
}

void Uproot(Tree* T) {
	void FreeNode(Node* N) {
		if (N == NULL) return;
		FreeNode(N->L);
		FreeNode(N->R);
		free(N);
	}
	if (T == NULL) return;
	FreeNode(T->root);
	free(T);
}

Tree* plant() {
	Tree* T;
	if ((T = malloc(sizeof(Tree))) == NULL) return NULL;
	T->count = 0;
	T->root = NULL;
	return T;
}

int main() {
	Tree* T = plant();
	
	Add(T, 4);
	Add(T, 2);
	Add(T, 7);
	Add(T, 6);
	Add(T, 8);
	Insert(T, 8, 3);
	Insert(T, 6, 2);
	Remove(T, 7);

	printf("The tree has %d elements and ", T->count);
	if (Find(T, 6) == NULL) printf("didn't"); else printf("did");
	printf(" find 6, and the value of 8 is %d.", Find(T,8)->value);
	Uproot(T);

	return 0;
}