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

#define EMPTY NULL
#define ARR_SIZE 10

struct btree {
	int data;
	struct btree *left;
	struct btree *right;
};

struct btree* add(struct btree * bt, int data) {
	if (bt) {
		if (bt->data < data) {
			bt->left = add(bt->left, data);
			return bt;
		}else if (bt->data > data) {
			bt->right = add(bt->right, data);
			return bt;
		}else {
			return bt;	
		}
	}else {
		struct btree * ans = (struct btree*)malloc(sizeof(struct btree));
		if (!ans) {
			fputs("alocation failed!\n", stderr);
			exit(1);
		}
		ans->data = data;
		ans->left = EMPTY;
		ans->right = EMPTY;
		return ans;
	}
}

void display(const struct btree * bt) {
	if (bt) {
		display(bt->left);
		fprintf(stdout, "%d\n", bt->data);
		display(bt->right);
	}else {
		fputs("EMPTY\n", stdout);
	}
}

const struct btree* find(const struct btree * bt, const int data) {
	if (bt) {
		if (bt->data < data) {
			return find(bt->left, data);
		}else if (bt->data > data) {
			return find(bt->right, data);
		}else {
			return bt;
		}
	}else {
		return bt;
	}
}

void freeBtree(struct btree * bt) {
	if (bt) {
		freeBtree(bt->left);
		freeBtree(bt->right);
		free(bt);
	}
}

struct btree* joinBranches(struct btree * left, struct btree * right) {
	if (!left) {
		return right;
	}else if (!right) {
		return left;
	}else {
		if (!right->left) {
			right->left = left;
			return right;
		}else {
			joinBranches(left, right->left);
			return right;
		}
	}
}

void removeNodeAux(struct btree ** bt, struct btree ** prev, bool left, const int data) {
	if (*bt) {
		if ((*bt)->data < data) {
			removeNodeAux(&(*bt)->left, bt, true, data);
		}else if ((*bt)->data > data) {
			removeNodeAux(&(*bt)->right, bt, false, data);
		}else {
			if (*prev) {
				struct btree * l = (*bt)->left;
				struct btree * r = (*bt)->right;
				free(*bt);
				if (left) {
					(*prev)->left = joinBranches(l, r);
				}else {
					(*prev)->right = joinBranches(l, r);
				}
			}else {
				struct btree * l = (*bt)->left;
				struct btree * r = (*bt)->right;
				free(*bt);
				(*bt) = joinBranches(l, r);
			}
		} 
	}
}

void removeNode(struct btree ** bt, const int data) {
	struct btree *prev = EMPTY;
	removeNodeAux(bt, &prev, false, data);
}

int main (int argc, char ** argv) {
	int data[ARR_SIZE] = {10, 1, 8, 2, 3, 9, 7, 5, 6, 4};
	struct btree * bt = EMPTY;
	size_t i = 0;

	for (; i < ARR_SIZE; i++) {
		bt = add(bt, data[i]);
	}

	display(bt);

	removeNode(&bt, 5);

	fputs("\n\n", stdout);

	display(bt);

	freeBtree(bt);

	return 0;
}