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

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

typedef struct treeNode* BSTree;


static struct treeNode* createNode(int data)
{
	struct treeNode *temp;
	temp = (struct treeNode*)calloc(1, sizeof(struct treeNode));
	assert(temp != NULL);
	temp->left = NULL;
	temp->right = NULL;
	temp->data = data;

	return temp;
}

void recursiveToArray(const BSTree tree, int arr[], int *temp)
{
	if (tree == NULL)
	{
		return;
	}

	else
	{

		recursiveToArray(tree->left, arr, temp);
		arr[*temp] = tree->data;
		temp++;
		recursiveToArray(tree->right, arr, temp);
	}

}

static int* writeSortedToArray(const BSTree tree)
{
	int size = countingNodes(&(*tree));
	int *arr;
	arr = (int*)calloc(size, sizeof(int));
	assert(arr != NULL);
	int *temp=arr;

	recursiveToArray(tree, arr, temp);
	for (int i = 0; i < 8; i++)
	{
		printf("%d\n", *(arr+i));
	}


    return arr;
}

void buildTree(BSTree* tree, int *arr, int start, int slut)
{


	if (start>slut)
	{
		return;
	}


	int mitten = ((start + slut) / 2);

	*tree = createNode(*(arr + mitten));


	buildTree(&(*tree)->right, arr, mitten+1, slut);
	buildTree(&(*tree)->left, arr, start, mitten-1);


}

/* Bygger upp ett sorterat, balanserat trad fran en sorterad array */
static void buildTreeSortedFromArray(BSTree* tree, const int arr[], int size)
{

	int start = 0, slut = size-1;



	/**tree = createNode(arr[mitten]);

	buildTreeSortedFromArray(&(*tree)->left, arr, mitten);
	buildTreeSortedFromArray(&(*tree)->right, arr, slut);*/
	buildTree(&(*tree), arr, start, slut);


}



{
	return NULL;
}

{
	if (tree == NULL)
		return 1;
	else
		return 0;
}



{
	if (*tree == NULL)
	{
		*tree=createNode(data);
	}
	else if((*tree)->data==data)
	{
		printf("Element already in tree.");
		return;
	}
	else if ((*tree)->data > data)
	{
		insertSorted(&(*tree)->left, data);
	}
	else if ((*tree)->data < data)
	{
		insertSorted(&(*tree)->right, data);
	}


	assert(find(*tree, data)==1);

}

int countingNodes(const BSTree tree)
{
	if (tree == NULL)
	{
		return 0;
	}
	if (tree->left == NULL && tree->right==NULL)
	{
		return 1;
	}
	else
	{
		int count = (countingNodes(tree->left) + countingNodes(tree->right)) + 1;
		return count;
	}
}


void printPreorder(const BSTree tree, FILE *textfile)
{

	if (tree == NULL)
	{
		return;
	}
	fprintf(textfile, "%d\t", tree->data);
	printPreorder(tree->left, textfile);
	printPreorder(tree->right, textfile);
}

void printInorder(const BSTree tree, FILE *textfile)
{

	if (tree == NULL)
	{
		return;
	}
	printInorder(tree->left, textfile);
	fprintf(textfile, "%d\t", tree->data);
	printInorder(tree->right, textfile);
}

void printPostorder(const BSTree tree, FILE *textfile)
{
	if (tree == NULL)
	{
		return;
	}

	printPostorder(tree->left, textfile);
	printPostorder(tree->right, textfile);
	fprintf(textfile, "%d\t", tree->data);
}


int find(const BSTree tree, int data)
{
	if (tree == NULL)
	{
		return 0;
	}
	else
	{
		if (tree->data == data)
		{
			return 1;
		}
		else if (tree->data > data)
		{
			return find(tree->left, data);
		}
		else
		{
			return find(tree->right, data);
		}
	}

}


void removeElement(BSTree* tree, int data)
{

	if (*tree == NULL)
	{
		printf("Tree is empty.\n");
		return;
	}
	if ((*tree)->data > data)
	{
		removeElement(&(*tree)->left, data);
	}
	else if ((*tree)->data < data)
	{
		removeElement(&(*tree)->right, data);
	}
	else
	{
		BSTree remove;
		if ((*tree)->left == NULL && (*tree)->right==NULL)
		{
			free(*tree);
			*tree = NULL;
		}
		else if ((*tree)->left != NULL && (*tree)->right == NULL)
		{
			remove = *tree;
			*tree = (*tree)->left;
			free(remove);
			remove = NULL;
		}
		else if ((*tree)->left == NULL && (*tree)->right != NULL)
		{
			remove = *tree;
			*tree = (*tree)->right;
			free(remove);
			remove = NULL;
		}
		else
		{
			BSTree minRight = (*tree)->right;
			while (minRight->left != NULL)
			{
				minRight = minRight->left;
			}
			(*tree)->data = minRight->data;
			removeElement(&(*tree)->right, minRight->data);
		}
	}

}


int numberOfNodes(const BSTree tree)
{
	int i = countingNodes(&(*tree));
	return i; //Ersatt med korrekt returvarde
}


int depth(const BSTree tree)
{

	if (tree == NULL)
	{
		return 0;
	}
	int vänsterDjup = depth(tree->left),
		högerDjup = depth(tree->right);
	if (vänsterDjup > högerDjup)
	{
		return(vänsterDjup + 1);
	}
	else
		return(högerDjup + 1);

}


int minDepth(const BSTree tree)
{
	float antal = countingNodes(&(*tree));
	double logRäkning = log2(antal + 1);
	logRäkning = ceil(logRäkning);
	return (int)logRäkning;

}

void balanceTree(BSTree* tree)
{
	int size = numberOfNodes(*tree);
		if (*tree == NULL)
		{
			return;
		}
	int arr;
	arr=writeSortedToArray(*tree);
	freeTree(&(*tree));
	buildTreeSortedFromArray(&(*tree), arr, size);

}


{
	if (*tree == NULL)
	{
		return;
	}
	else
	{
		freeTree(&(*tree)->left);
		freeTree(&(*tree)->right);
		free(*tree);
		*tree = NULL;
	}

}