#include <iostream.h>

class BST
{

private:
	typedef struct node { 
	int key, info;  node *l , *r;} tnode;
    
	tnode *head, *z;
	void treeprintr(tnode *x);

public:
	BST()
	{
        z = new tnode;
		z->key = 0;
		z->info = -1;
		z->l = z;
		z->r = z;
		head  = new tnode;
		head->info = 0;
		head->key = 0;
		head->l = 0; 
		head->r = z; 
	}

	~BST(){};
    int treesearch(int v);
    void treeinsert(int v);
    void treeprint(void);
};


int BST::treesearch(int v)
{
   tnode *x = head->r;
   z->key = v;

   while (v != x->key)
   if (v < x->key)
     x = x->l;
   else
     x = x->r;
   return x-> info;
} 

void BST::treeprint(void)
{
	treeprintr(head->r);
}

void BST::treeprintr(tnode *x)
{
   if (x!=z)
   {    treeprintr(x->l);
        cout<<"\n" << x->key;
        treeprintr(x->r);
   }
}



void BST::treeinsert(int v)
//do a search for pointer to empty node first - traversing using item as key
//remember the node address which contains this pointer (call it p).
//create new node
//place data item in new node and set l,r pointers to z (our terminator node)
//now set p's left pointer or right pointer to point to new node. 
//left if item is less than p's key, else right.
//set info to 0 in new node.
{
   tnode *x, *p;
   p = head; x = head->r;
   while (x != z)    //terminator node found?
   {
	 p=x;
	 if (v < x->key)
        x = x->l;
     else
        x = x->r;
   }
   x = new tnode;  //x points to new node
   x->key = v;  //set data item in new node pointee to by x
   x->info  = 0;  //set info to 0
   x->l = z; x->r=z;  //set pointers to terminator node for time being
   if(v< p->key)    //decide if new data item is to go to left or right of last node.
	    p->l = x;
   else 
	    p->r = x;
}


int main (void)
{
	BST mytree;
    mytree.treeinsert(4);
    mytree.treeinsert(1);
    mytree.treeinsert(7);
    mytree.treeinsert(9);
    mytree.treeinsert(2);
    mytree.treeprint();

	if (mytree.treesearch(7) == 0)
		cout << "\nfound\n";
	else
		cout<< "\n not found \n";

    return 0;
}