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

int arrLen = 5;
int maxdepth = 0;
int mindepth = 10;
int totalElem = 8;

typedef struct BST {
    int data;
    struct BST *left;
    struct BST *right;
} nodeBST;

void balanceBST(int arr[]);
nodeBST* addNode(int data);
void addNodeToBST(nodeBST *root, nodeBST *node);
void traverse(nodeBST *root);
void maxDepth(nodeBST *root, int depth);
void minDepth(nodeBST *root, int depth);

int maxDepthWithoutGlobalVar(nodeBST *root, int depth, int maxDeep);
int minDepthWithoutGlobalVar(nodeBST *root, int depth, int minDeep);

int main()
{
    int arr[10] = {5,3,7,10,6,12,2,1};

    (void)balanceBST(arr);

    return 0;
}

void balanceBST(int arr[])
{
    nodeBST *node;
    nodeBST *root;
    int max = 0;
    int min = 100000;
    int i = 0;

    for (i = 0; i < totalElem; i++) {
	node = addNode(arr[i]);
	if (node == NULL) {
	    return;
	}

	if (i == 0) {
	    root = node;
	    continue;
	}

	addNodeToBST(root, node);
    }

    printf("Nodes created\n");
    traverse(root);
    maxDepth(root, 0);
    printf("\nMax Depth %d\n", maxdepth);
    minDepth(root, 0);
    printf("Min Depth %d\n\n", mindepth);

    max = maxDepthWithoutGlobalVar(root, 0, max);
    printf("Max Depth %d\n", max);

    min = minDepthWithoutGlobalVar(root, 0, min);
    printf("Min Depth %d\n", min);

    if ((max - min) > 1) {
	printf("Binary search tree is not Balanced\n");
    } else {
	printf("Binary search tree is Balanced\n");
    }
}

nodeBST* addNode(int data)
{
    nodeBST *node = (nodeBST*)calloc(1, sizeof(nodeBST));

    if (node == NULL) {
	return NULL;
    }

    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return node;
}

void addNodeToBST(nodeBST *root, nodeBST *node)
{
    while(root != NULL) {
	if (node->data < root->data) {
	    if (root->left != NULL) {
		root = root->left;
	    } else {
		root->left = node;
		return;
	    }
	} else {
	    if (root->right != NULL) {
		root = root->right;
	    } else {
		root->right = node;
		return;
	    }
	}
    }

    return;
}

void traverse(nodeBST *root)
{
    if (root == NULL) {
	return;
    } else {
	traverse(root->left);
	printf("%d ", root->data);
	traverse(root->right);
    }

    return;
}

void maxDepth(nodeBST *root, int depth)
{
    if (root == NULL) {
	if (maxdepth < depth) {
	    maxdepth = depth;
	}
    } else {
	maxDepth(root->left, (depth + 1));
	maxDepth(root->right, (depth + 1));
    }
}

void minDepth(nodeBST *root, int depth)
{
    if (root == NULL) {
	if (mindepth > depth) {
	    mindepth = depth;
	}
    } else {
	minDepth(root->left, (depth + 1));
	minDepth(root->right, (depth + 1));
    }
}

int maxDepthWithoutGlobalVar(nodeBST *root, int depth, int maxDeep)
{
    if (root == NULL) {
	if (maxDeep <= depth) {
	    maxDeep = depth;
	}
	return maxDeep;
    } else {
        maxDeep = maxDepthWithoutGlobalVar(root->left, (depth + 1), maxDeep);
	maxDeep = maxDepthWithoutGlobalVar(root->right, (depth + 1), maxDeep);
    }

    return maxDeep;
}

int minDepthWithoutGlobalVar(nodeBST *root, int depth, int minDeep)
{
    if (root == NULL) {
	if (minDeep >= depth) {
	    minDeep = depth;
	}
	return minDeep;
    } else {
        minDeep = minDepthWithoutGlobalVar(root->left, (depth + 1), minDeep);
	minDeep = minDepthWithoutGlobalVar(root->right, (depth + 1), minDeep);
    }

    return minDeep;
}