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

	typedef struct node {
		int data;
		struct node *left, *right;
	} node;

	typedef struct BST {
		struct node *root;
	} BST;

	// Function Prototypes
	BST *createBST();
	node *createNode(int data);
	void addNodeRecWrapper(BST *bst, int data);
	node *addNodeRec(node *root, node *newNode);
	void addNodeIterative(BST *bst, int data);
	int nodeExists(BST *bst, int target);
	node *targetNodeParent(node *root, int target);
	int deleteNode(BST *bst, int data);
	node *minNode(node *root);
	void printPreorder(node *root);
	void printInorder(node *root);
	void printPostorder(node *root);
	int smallestValue(node *root);
	void printOptions();
	void freeBST(BST *bst);
	void freeBSTNodes(node *root);

	// Initialize BST struct
	BST *createBST() {
		BST *b = malloc(sizeof(BST));
		b->root = NULL;
		return b;
	}

	// Initialize BST node
	node *createNode(int data) {
		node *n = malloc(sizeof(node));
		n->data = data;
		n->left = NULL;
		n->right = NULL;
		return n;
	}

	// Calls recursive addNodeRec function
	void addNodeRecWrapper(BST *bst, int data) {
		if (!bst)
			return;
		node *newNode = createNode(data);
		bst->root = addNodeRec(bst->root, newNode);
	}

	// Recursively traverses the BST to find the correct insertion position
	// Once a NULL child pointer is reached, the new node is inserted as a leaf
	node *addNodeRec(node *root, node *newNode) {
		if (!root)
			return newNode;

		if (newNode->data < root->data)
			root->left = addNodeRec(root->left, newNode);
		else
			root->right = addNodeRec(root->right, newNode);

		return root;
	}

	// Iterative version of adding a BST node
	// Not called by menu in main
	void addNodeIterative(BST *bst, int data) {
		if (!bst)
			return;

		node *newNode = createNode(data);

		if (!(bst->root)) {
			bst->root = newNode;
			return;
		}
		node *walker = bst->root;
		while (walker) {
			if (data < walker->data) {
				if (walker->left) {
					walker = walker->left;
				} else {
					walker->left = newNode;
					return;
				}
			} else {
				if (walker->right) {
					walker = walker->right;
				} else {
					walker->right = newNode;
					return;
				}
			}
		}
	}

	// Returns 1 if node exists in list
	// Otherwise returns 0
	int nodeExists(BST *bst, int target) {
		if (!bst || !(bst->root))
			return 0;
		return (bst->root->data == target) || targetNodeParent(bst->root, target);
	}

	// Returns the parent node of node with specified target data value
	// If no such node exists, returns NULL
	node *targetNodeParent(node *root, int target) {
		if (!root)
			return NULL;

		if (root->left && root->left->data == target)
			return root;
		else if (root->right && root->right->data == target)
			return root;

		if (target < root->data)
			return targetNodeParent(root->left, target);
		else
			return targetNodeParent(root->right, target);
	}

	// Deletes a node with target data value
	// Assumes no duplicates exist
	int deleteNode(BST *bst, int target) {
		if (!bst || !(bst->root))
			return 0;

		node *parent;
		if (bst->root->data == target)
			parent = NULL;
		else {
			parent = targetNodeParent(bst->root, target);
			if (!parent)
				return 0;
		}

		node *delNode;
		// If !parent, target is at root
		if (!parent)
			delNode = bst->root;
		else
			delNode = target < parent->data ? parent->left : parent->right;

		// Check if leaf node
		if (!(delNode->left) && !(delNode->right)) {
			if (parent) {
				if (target < parent->data) {
					parent->left = NULL;
				} else {
					parent->right = NULL;
				}
			} else {
				bst->root = NULL;
			}
			free(delNode);
		}
		// Left child only
		else if (!(delNode->right)) {
			if (parent) {
				if (target < parent->data) {
					parent->left = delNode->left;
				} else {
					parent->right = delNode->left;
				}
			} else {
				bst->root = delNode->left;
			}
			free(delNode);
		}
		// Right child only
		else if (!(delNode->left)) {
			if (parent) {
				if (target < parent->data) {
					parent->left = delNode->right;
				} else {
					parent->right = delNode->right;
				}
			} else {
				bst->root = delNode->right;
			}
			free(delNode);
		}
		// node has two children
		else {
			node *minRight = minNode(delNode->right);
			int newDataAtDel = minRight->data;
			deleteNode(bst, newDataAtDel);
			delNode->data = newDataAtDel;
		}
		return 1;
	}

	// Returns pointer to the smallest node of given sub-tree
	// If root is NULL, returns NULL
	node *minNode(node *root) {
		if (!root)
			return NULL;
		if (root->left)
			return minNode(root->left);
		return root;
	}

	// Prints in preorder
	void printPreorder(node *root) {
		if (!root)
			return;
		printf("%d ", root->data);
		printPreorder(root->left);
		printPreorder(root->right);
	}

	// Prints in inorder
	void printInorder(node *root) {
		if (!root)
			return;
		printInorder(root->left);
		printf("%d ", root->data);
		printInorder(root->right);
	}

	// Prints in postorder
	void printPostorder(node *root) {
		if (!root)
			return;
		printPostorder(root->left);
		printPostorder(root->right);
		printf("%d ", root->data);
	}

	// Returns smallest data value in tree
	int smallestValue(node *root) {
		return !(root->left) ? root->data : smallestValue(root->left);
	}

	// Print options menu
	void printOptions() {
		printf("1) Add data to BST\n");
		printf("2) Delete data from BST\n");
		printf("3) Check if data is in BST\n");
		printf("4) Print BST preorder\n");
		printf("5) Print BST inorder\n");
		printf("6) Print BST postorder\n");
		printf("7) Print smallest value in tree\n");
		printf("8) Quit\n");
		printf("\n:");
	}

	// Frees BST
	void freeBST(BST *bst) {
		if (!bst)
			return;
		freeBSTNodes(bst->root);
		free(bst);
	}

	// Frees all nodes within a BST
	void freeBSTNodes(node *root) {
		if (!root)
			return;
		freeBSTNodes(root->left);
		freeBSTNodes(root->right);
		free(root);
	}

	int main(void) {
		BST *binSearchTree = createBST();

		int choice = 0;
		int data;

		while (choice != 8) {
			printOptions();
			scanf("%d", &choice);

			switch (choice) {

			case 1: // Add data
				printf("Enter an integer to add to the tree\n:");
				scanf("%d", &data);
				if (!nodeExists(binSearchTree, data)) {
					addNodeRecWrapper(binSearchTree, data);
					printf("%d added to list\n", data);
				} else {
					printf("%d is already in the tree\n", data);
				}
				break;

			case 2: // Delete data
				printf("Enter an integer to delete from the tree\n:");
				scanf("%d", &data);
				if (nodeExists(binSearchTree, data)) {
					deleteNode(binSearchTree, data);
					printf("%d deleted\n", data);
				} else
					printf("%d is not in the tree\n", data);
				break;

			case 3: // Does data exist?
				printf("Enter an integer to check if it exists in the tree\n:");
				scanf("%d", &data);
				printf("%d is %sin the tree\n", data,
							 nodeExists(binSearchTree, data) ? "" : "NOT ");
				break;

			case 4: // Print tree preorder
				printf("\nPrinting BST preorder\n\n ");
				printPreorder(binSearchTree->root);
				printf("\n");
				break;

			case 5: // Print tree inorder
				printf("\nPrinting BST inorder\n\n ");
				printInorder(binSearchTree->root);
				printf("\n");
				break;

			case 6: // Print tree postorder
				printf("\nPrinting BST postorder\n\n");
				printPostorder(binSearchTree->root);
				printf("\n");
				break;

			case 7: // Print smallest value in tree
				if (binSearchTree->root) {
					printf("\nThe smallest value in the tree is: %d\n",
								 smallestValue(binSearchTree->root));
				} else {
					printf("\nThe tree is currently empty\n");
				}
				break;

			default:
				break;
			}
			printf("\n");
		}

		freeBST(binSearchTree);

		return 0;
	}