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

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

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;
}

// 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");

	return 0;
}