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

class NODE
{
public:
	NODE(int data)
	{
		left=NULL;
		right=NULL;
		this->data=data;
	}
	int data;
	NODE *left;
	NODE *right;
};

NODE *root;

bool addnode(NODE **currentnode,int data)
{
	if (*currentnode==NULL)
	{
		*currentnode=new NODE(data);
		return true;
	}
	else
	{
		if (data < (*currentnode)->data)
		{
			addnode( &((*currentnode)->left) ,data);
		}
		else if (data > (*currentnode)->data )
		{
			addnode( &((*currentnode)->right) ,data);
		}
	}
	return true;
}

void removeallnodes( NODE *node)
{
	if (node!=NULL)
	{
		removeallnodes(node->left);
		removeallnodes(node->right);
		delete node;
	}
}

void preorder(NODE *node)
{
	if (node!=NULL)
	{
		printf("%d ",node->data);
		preorder(node->left);		
		preorder(node->right);
	}
}

void inorder(NODE *node)
{
	if (node!=NULL)
	{
		inorder(node->left);
		printf("%d ",node->data);
		inorder(node->right);
	}
}

void postorder(NODE *node)
{
	if (node!=NULL)
	{
		postorder(node->left);		
		postorder(node->right);
		printf("%d ",node->data);
	}
}

void findnode(NODE *node,int what)
{
	if (node!=NULL)
	{
		printf("#");
		if (what>node->data)
			findnode(node->right,what);
		else if (what<node->data)
			findnode(node->left,what);
		else
			printf("Found %d\n",node->data);
	}
}

void main()	
{
	root=NULL;

	srand(unsigned(NULL));

	for (int i=0;i<50;i++)
	{
		addnode(&root,rand()%500);
	}

	printf("INORDER = ");
	inorder(root);
	printf("\n");

	int what;
	do
	{
		printf("What u want to find ");
		scanf("%d",&what);
		if (what!=0)
		{
			findnode(root,what);
		}
	}while(what!=0);

	removeallnodes(root);
}