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

/**
 * Exercise 1: programming in the C language
 * Using the C language, write a program that:
 *    - fills an array with random integers in the range 10 to 99.
 *    - builds a binary search tree by inserting the integers in the array into a tree.
 * 	  - finds the length of a given BST.
 *    - finds the number of leaf nodes.
 *    - finds the minimum value in a given BST.
 *    - prints the BST in 2D in reverse in-order traversal.
 *    - traverses the tree with pre-order, in-order, and post-order algorithms, printing each value in the tree along the way.
 *
 * author: Nicholas Adamou
 * date: 9/24/19
 * Class: CSC-315
 */

typedef struct node Node;

#define SIZE 10 // number of nodes in the BST
#define COUNT 4 // default number of spaces

struct node
{
	int value;   // node will store an integer
	Node *right; // right child
	Node *left;  // left child
};

// function to create a node
Node *new_node(int x)
{
	Node *p = malloc(sizeof(Node));

	p->value = x;
	p->left = NULL;
	p->right = NULL;

	return p;
}

Node *insert(Node *root, int x)
{
	// searching for the place to insert
	if (root == NULL)
		return new_node(x);
	else if (x > root->value) // x is greater. Should be inserted to right
		root->right = insert(root->right, x);
	else // x is smaller. Should be inserted to left
		root->left = insert(root->left, x);
	return root;
}

// Function to print binary tree in 2D
// It does reverse in-order traversal
void print2DUtil(Node *root, int depth)
{
	if (root == NULL) // Base case
		return;

	depth += COUNT; // Increase distance between levels

	print2DUtil(root->right, depth); // Process right child first

	// Print current node after space count
	printf("\n");
	for (int i = COUNT; i < depth; i++)
		printf(" ");
	printf("%d\n", root->value);

	print2DUtil(root->left, depth); // Process left child last
}

// Wrapper over print2DUtil()
void print2D(Node *root)
{
	// Pass initial depth as 0
	print2DUtil(root, 0);
}

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

int getNumberOfLeafNodes(Node *node)
{
	if (node == NULL)
		return 0;

	if (node->left == NULL && node->right == NULL)
		return 1;
	else
	{
		return getNumberOfLeafNodes(node->left) +
			   getNumberOfLeafNodes(node->right);
	}
}

// function to find the minimum value in a node
Node *findMinimum(Node *root)
{
	if (root == NULL)
		return NULL;
	else if (root->left != NULL)		 // node with minimum value will have no left child
		return find_minimum(root->left); // left most element will be minimum

	return root;
}

void preorder(Node *root)
{
	if (root != NULL) // checking if the root is not null
	{
		printf(" %d ", root->value); // printing value at root
		preorder(root->left);		 // visiting left child
		preorder(root->right);		 // visiting right child
	}
}

void inorder(Node *root)
{
	if (root != NULL) // checking if the root is not null
	{
		inorder(root->left);		 // visiting left child
		printf(" %d ", root->value); // printing value at root
		inorder(root->right);		 // visiting right child
	}
}

void postorder(Node *root)
{
	if (root != NULL) // checking if the root is not null
	{
		postorder(root->left);		 // visiting left child
		postorder(root->right);		 // visiting right child
		printf(" %d ", root->value); // printing value at root
	}
}

int main()
{
	int n; // random number

	int min = 10; // min number a given node can hold
	int max = 99; // max number a given node can hold

	Node *root = new_node(rand() % (max - min + 1) + min);

	srand(time(0)); // Use current time as seed for random generator

	for (int i = 0; i < SIZE; i++)
	{
		n = (rand() % (max - min + 1) + min);

		insert(root, n);
	}

	printf("Preorder traversal of the BST:\n");
	preorder(root);
	printf("\n\n");

	printf("Inorder traversal of the BST:\n");
	inorder(root);
	printf("\n\n");

	printf("Postorder traversal of the BST:\n");
	postorder(root);
	printf("\n\n");

	printf("Number of Nodes: %d\n", getFullCount(root));

	printf("Number of Leaf Nodes: %d\n", getLeafCount(root));

	printf("Minimum value: %d\n", findMinimum(root)->value);

	print2D(root);

	return 0;
}