#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...w.studyalgorithms,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 findElementInTreeRecursive(struct binaryTreeNode * root, int num)
{
	// A variable for root value
	int root_val;
	
	// Variable to store values in left and right tree
	int left, right;
	
	if(root != NULL)
	{
		// Get the root value
		root_val = root -> data;
		
		if(root_val == num)
			return 1;
		
		// Find the element in left sub-tree
		// If found, we return 1
		left = findElementInTreeRecursive(root -> left, num);
		if(left == 1)
			return 1;
		else
		{
			// We need to find the element in right sub-tree
			right = findElementInTreeRecursive(root -> right, num);
			if(right == 1)
				return 1;
		}
	}
	
	// If we reach here, that means the element was not found
	return 0;
}

int findElementInTreeNonRecursive(struct binaryTreeNode * root, int num)
{
	int found = 0;
	
	// Level Order Traversal
	struct binaryTreeNode * temp = NULL;
	struct queue * Q = NULL;
	if(root == NULL)
		return;
		
	Q = enQueue(Q, root);
	
	while(!isQueueEmpty(Q))
	{
		temp = Q -> front -> data;
		
		Q = deQueue(Q);

		// Find the element
		if(temp -> data == num)
		{
			found = 1;
			break;
		}
		
		if(temp -> left)
			Q = enQueue(Q, temp -> left);
		if(temp -> right)
			Q = enQueue(Q, temp -> right);
	}
	free(Q);
	
	// Return 1 if element was found
	return found;
}

// 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;
	
	// recursive version
	if(findElementInTreeRecursive(root, 90))
		printf("PRESENT");
	else
		printf("NOT PRESENT");
	
	printf("\n");
	
	// Non-recursive version
	if(findElementInTreeNonRecursive(root, 90))
		printf("PRESENT");
	else
		printf("NOT PRESENT");

	return 0;
}