#include<iostream>

using namespace std;

struct tree
 {
  int data;
  tree *left;
  tree *right;
 }
 
  *sptr, *q; // two pointers with no specific type
 
  void rightcheck();
  void leftcheck();
  void search();

  int insdata;
  tree *node;
  
  int main()
   {
    node=new tree;
    cout<<"Enter a root value: ";
    cin>>node->data;
    sptr=node;
    q=sptr;
    node->left=NULL;
    node->right=NULL;
    cout<<"Enter Left child value: ";
    cin>>insdata;
    search();
    while(insdata!=0)
	{
	 if(insdata>sptr->data)
	    rightcheck();
	 else
	    leftcheck();
	    cout<<"Enter Right child value: ";
	    cin>>insdata;
	    search();
	    sptr=node;
       }
      getchar();
      }
      
     void rightcheck()
       {
	 if(sptr->right==NULL)
	   {
	    cout<<"    "<<insdata<<" IS THE  RIGHT  child of "<<q->data<<endl;
	    sptr->right=new tree;
	    sptr=sptr->right;
	    sptr->data=insdata;
	    sptr->left=NULL;
	    sptr->right=NULL;
	    q=node;
	   }
	 else
	    {
	     if(insdata>sptr->data)
	      {
	       sptr=sptr->right;
	       q=sptr;
	       if(insdata>sptr->data)
		rightcheck();
		else
		leftcheck();
	     }
	     else
	      {
		sptr=sptr->left;
		q=sptr;
		leftcheck();
	      }
	     }
	}
		 void leftcheck()
	{
		 if(sptr->left==NULL)
		  {
		   cout<<"   "<<insdata<<" IS THE LEFT child of "<<q->data<<endl;
		   sptr->left=new tree;
		   sptr=sptr->left;
		   sptr->data=insdata;
		   sptr->right=NULL;
		   sptr->left=NULL;
		   q=node;
		  }
	 else{
	     if(insdata<sptr->data)
	      {
		sptr=sptr->left;
		q=sptr;
		if(insdata>sptr->data)
		rightcheck();
		else
		leftcheck();
	      }
	     else
	      {
		sptr=sptr->right;
		q=sptr;
		rightcheck();}
	      }
	}

       void search()
	{
	   sptr=node;
	   while(sptr!=NULL)
	{
	  if(insdata==sptr->data)
	    {
	    cout<<"This is not insertable.";
	    cout<<"\nInsert child ";
	    cin>>insdata;
	    search();
	    break;
	    }
	  else
	  {
	    if(insdata>sptr->data)
		sptr=sptr->right;
	    else
		sptr=sptr->left;
	 }
       }
	 sptr=node;
     
       }