#include<stdio.h>
#include<malloc.h>

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

struct node
{
	struct binaryTreeNode * data;
	struct node * next;
};

struct queue
{
	struct node * front;
	struct node * rear;
};

struct queue * enQueue(struct queue * q, struct binaryTreeNode * num)
{
	struct node * temp = (struct node*)malloc(sizeof(struct node));
	temp -> data = num;
	temp -> next = NULL;
	if(q == NULL)
	{
		q = (struct queue*)malloc(sizeof(struct queue));		
		q -> front = temp;
	}
	else
		q -> rear -> next = temp;
	q -> rear = temp;
	//Code obtained from http://w...content-available-to-author-only...s.com
	//Feel free to copy but please acknowledge the site wherever possible
	return q;
}

struct queue * deQueue(struct queue * q)
{
	struct node * temp = q->front;
	q -> front = q->front->next;
	free(temp);
	if(q->front == NULL)
		return NULL;
	else
		return q;
}

int isQueueEmpty(struct queue * q)
{
	if(q)
		return 0;
	else
		return 1;
}

int heightOfBinaryTreeRecursive(struct binaryTreeNode * root)
{
	// Initialize 2 variables for left and right height
	int leftHeight;
	int rightHeight;
	
	// The terminating case
	if(root == NULL)
		return 0;
	else
	{
		// Find the depth of left sub-tree
		leftHeight = heightOfBinaryTreeRecursive(root -> left);
		
		// Find the depth of right sub-tree
		rightHeight = heightOfBinaryTreeRecursive(root -> right);
		
		// Compare the two heights and return the larger of two + 1
		if(leftHeight > rightHeight)
		{
			// Return the leftHeight + 1
			return (leftHeight + 1);
		}
		else
		{
			// Return the rightHeight + 1
			return (rightHeight + 1);
		}
	}
}

int heightOfBinaryTree(struct binaryTreeNode * root)
{
	// Level order traversal
	struct binaryTreeNode * temp = NULL;
	struct queue * Q = NULL;
	
	// Maintain a level count
	int level = 0;

	if(root == NULL)
		return 0;

	Q = enQueue(Q, root);
	// Now the first level will end over here,
	// So append a NULL node
	Q = enQueue(Q, NULL);
	
	while(!isQueueEmpty(Q))
	{
		temp = Q -> front -> data;
		Q = deQueue(Q);
		
		// If we encounter a NULL, that means an end of a level
		// And we need to increment the level count
		if(temp == NULL)
		{
			// Put the marker for next level also
			if(!isQueueEmpty(Q))
				Q = enQueue(Q, NULL);
			
			level++;
		}
		else
		{
			// We continue with the level order traversal
			if(temp -> left)
				Q = enQueue(Q, temp -> left);
			if(temp -> right)
				Q = enQueue(Q, temp -> right);
		}
	}
	// Delete the queue
	free(Q);
	
	// Now return the count
	return level;
}

// Test the above functions
int main(void)
{
	// Initialize the tree
	struct binaryTreeNode * root = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
	root-> data = 1;
	struct binaryTreeNode * l = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
	l -> data = 2;
	struct binaryTreeNode * ll = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
	ll -> data = 4;
	ll -> left = ll -> right = NULL;
	struct binaryTreeNode * lr = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
	lr -> data = 5;
	lr -> left = lr -> right = NULL;
	l -> left = ll;
	l -> right = lr;
	struct binaryTreeNode * r = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
	r -> data = 3;
	struct binaryTreeNode * rl = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
	rl -> data = 6;
	rl -> left = rl -> right = NULL;
	struct binaryTreeNode * rr = (struct binaryTreeNode *)malloc(sizeof(struct binaryTreeNode));
	rr -> data = 7;
	rr -> left = rr -> right = NULL;
	r -> left = rl;
	r -> right = rr;
	root -> left = l;
	root -> right = r;
	
	printf("Height of the binary tree = %d",heightOfBinaryTree(root));

	return 0;
}