#include <iostream>
using namespace std;

typedef struct node
{
	int key;
	int noChildren;
	struct node* left;
	struct node* right;
}node;

node* newNode(int value);
int size(node* root);
node* OS_BUILD_TREE(int values[], node* root, int low, int high);
node* OS_SELECT(node* root, int i);
node* OS_DELETE(node* root, int val);
node* minNode(node* root);
void preOrder(node* root);

int main()
{
	int values[] = { 2, 14, 27, 28, 39, 42, 45, 55, 58, 97 };
	int n = sizeof(values) / sizeof(values[0]);
	node* root = NULL;
	root = OS_BUILD_TREE(values, root, 0, n-1);
	preOrder(root);
	cout << '\n';
	node* toSearch = OS_SELECT(root, 5);
	cout << toSearch->key;
	cout << '\n';
	node* toDelete = OS_DELETE(root, 14);
	node* toDelete1 = OS_DELETE(root, 55);
	node* toDelete2 = OS_DELETE(root, 45);
	node* toDelete3 = OS_DELETE(root, 28);
	preOrder(root);
}

node* newNode(int value)
{
	node* temp = (node*)malloc(sizeof(node));
	temp->key = value;
	temp->noChildren = 0;
	temp->left = NULL;
	temp->right = NULL;
	return temp;
}

int size(node* root)
{
	if (root == NULL)
		return 0;
	else
		return(size(root->left) + size(root->right) + 1);
}

node* OS_BUILD_TREE(int values[], node* root, int low, int high)
{
	if (low > high)
	{
		return 0;
	}
	int mid = (low + high) / 2;
	root = newNode(values[mid]);
	root->left = OS_BUILD_TREE(values, root->left, low, mid - 1);
	root->right = OS_BUILD_TREE(values, root->right, mid + 1, high);
	if ((root->left == NULL) && (root->right == NULL))
	{
		root->noChildren = 1;
	}
	else
	{
		root->noChildren = size(root);
	}
	return root;

}

node* OS_SELECT(node* root, int i)
{
	int left_size;
	if (root->left == NULL)
		left_size = 0;
	else
		left_size = root->left->noChildren;
	if (left_size + 1 == i)
		return root;
	else if (left_size + 1 < i)
		return OS_SELECT(root->right, i - left_size - 1);
	else
		return OS_SELECT(root->left, i);
}

node* minNode(node* root)
{
	node* current = root;
	while (current->left != NULL)
	{
		current = current->left;
	}
	return current;
}

node* OS_DELETE(node* root, int val)
{
	if (root == NULL)
	{
		return root;
	}
	if (val < root->key)
	{
		root->left = OS_DELETE(root->left, val);
		root->noChildren -= 1;
	}
	else if (val > root->key)
	{
		root->right = OS_DELETE(root->right, val);
		root->noChildren -= 1;
	}
	else
	{
		if (root->left == NULL)
		{
			node* temp = root->right;
			free(root);
			return temp;
			root->noChildren -= 1;
		}
		else if (root->right == NULL)
		{
			node* temp = root->left;
			free(root);
			return temp;
			root->noChildren -= 1;
		}

		node* temp = minNode(root->right);
		root->key = temp->key;
		root->right = OS_DELETE(root->right, temp->key);
		root->noChildren -= 1;
	}
	return root;
}

void preOrder(node* root)
{
	if (root != NULL)
	{
		cout << root->key << "," << root->noChildren << "   ";
		preOrder(root->left);
		preOrder(root->right);
	}
}