#include<stdio.h>
#include<stdlib.h>
struct node
{
	int element;
	struct node *left;
	struct node *right;
	struct node *parent;
};
typedef struct node *Tree;
Tree insert_number(int number,Tree t)
{
	if(t==NULL)
	{
		t=(Tree)malloc(sizeof(struct node));
		t->element=number;
		t->left=NULL;
		t->right=NULL;
		t->parent=NULL;
		printf("Number inserted\n");
		return t;
	}
	else
	{
	
		if(t->element == number)
		{
			printf("Number already present\n");
			return t;
		}
		else if(t->element > number)
		{
			t->left=insert_number(number,(t->left));
			t->left->parent=t;
			return t;
		}
		else if(t->element < number)
		{
			t->right=insert_number(number,(t->right));
			t->right->parent=t;
			return t;
		}
	}
}
	
	
	
		

Tree search_number(int number,Tree t)
{	
	if(t == NULL)
    {
		printf("No such element exists\n");
	    return NULL;
	}
	if(number==t->element)
	{
		printf("Element found\n");
		return t;
	}
    if(number < t->element)
	{
		return search_number(number,t->left);
	}
	if(number > t->element)
	{
		return search_number(number,t->right);
	}
	
}
int main()
{
	int n;
	Tree t,ret;
	t=NULL;
	char ch='a';
	printf("Enter the sequence of operations:\n");
	printf("To insert:i (number)\nTo search:s (number)\nTo exit:e\n");
	do
	{
		scanf("%c",&ch);
		if(ch=='i')
		{
			scanf("%d",&n);
			t=insert_number(n,t);
		}
		else if(ch=='s')
		{
			scanf("%d",&n);
			ret=search_number(n,t);
		}
		else if(ch=='e')
			break;
		else
			printf("Invalid choice\n");
		getchar();
	}while(1);
	return 0;
}