// Creating and traversing abinary tree
// Preorder , inorder , and postorder

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

struct treeNode {
	struct treeNode* leftPtr; // pointer to left subtree
	int data; // node value
	struct treeNode* rightPtr; // pointer to right subtree
};

typedef struct treeNode TreeNode;
typedef TreeNode* TreeNodePtr;

void insertNode(TreeNodePtr* treePtr, int value);
void inOrder(TreeNodePtr treePtr);
void preOrder(TreeNodePtr treePtr);
void postOrder(TreeNodePtr treePtr);

int main()
{
	int i; // counter to loop 1-10
	int item; // varaible to hold random values
	TreeNodePtr rootPtr = NULL; // tree initially empty

	srand(time(NULL));
	printf("The numbers being placed in the tree are : ");

	// insert random values between 0 and 14 in the tree
	for (i = 0; i <= 10; i++)
	{
		item = rand() % 15;
		printf("  %d", item);
		insertNode(&rootPtr, item);
	}

	// traverse hte tree preOrder
	printf("\n\nThe preOrder traversal is : ");
	preOrder(rootPtr);

	// traverse hte tree inOrder
	printf("\n\nThe inOrder traversal is : ");
	inOrder(rootPtr);

	// traverse hte tree preOrder
	printf("\n\nThe postOrder traversal is : ");
	postOrder(rootPtr);
	printf("\n");
	return 0;
}

void insertNode(TreeNodePtr* treePtr, int value)
{
	if (*treePtr == NULL) // if tree is empty or the correct location has been found
	{
		*treePtr = malloc(sizeof(TreeNode));

		// if the memory is allocated , then assign data
		if (*treePtr != NULL)
		{
			(*treePtr)->data = value;
			(*treePtr)->leftPtr = NULL;
			(*treePtr)->rightPtr = NULL;
		}
		else
		{
			printf("%d not inserted. No memory avaliable.\n", value);
		}
	}
	else // tree is not empty
	{
		if (value <= (*treePtr)->data) // data to insert is less than data in the current node
		{
			insertNode(&((*treePtr)->leftPtr), value);
		}
		else if (value > (*treePtr)->data) // data to insert is greater than data in the current node
		{
			insertNode(&((*treePtr)->rightPtr), value);
		}
		else // duplicate data value ignored
		{
			printf("dup");
		}
	}
} // end function insertNode

void inOrder(TreeNodePtr treePtr)
{
	// if tree is not empty , then traverse
	if (treePtr != NULL)
	{
		inOrder(treePtr->leftPtr);
		printf("%d  ", treePtr->data);
		inOrder(treePtr->rightPtr);
	}
}

void preOrder(TreeNodePtr treePtr)
{
	// if tree is not empty , then traverse
	if (treePtr != NULL)
	{
		printf("%d  ", treePtr->data);
		preOrder(treePtr->leftPtr);
		preOrder(treePtr->rightPtr);
	}
}

void postOrder(TreeNodePtr treePtr)
{
	// if tree is not empty , then traverse
	if (treePtr != NULL)
	{
		postOrder(treePtr->leftPtr);
		postOrder(treePtr->rightPtr);
		printf("%d  ", treePtr->data);
	}
}