#include<iostream>
using namespace std;
class node
{
int element1,element2,element3;
node *left,*right,*middle,*parent;
public:
node()
{
element1=-1;
element2=-1;
element3=-1;
}
node *insert(node *,int);
node *search(node*,int);
void preorder(node*);
void balance(node *);
};

void node::balance(node* root)
{
    node *temp=new node;
if(temp->parent==NULL)//this is the first node
    {
        node *temp1=new node;
        node *temp2=new node;


        temp1->parent=temp;//linking
        temp1->left=NULL;
        temp1->right=NULL;
        temp1->middle=NULL;
        temp2->parent=temp;//linking
        temp2->left=temp->left;
        temp2->right=NULL;
        temp2->middle=NULL;//NO DUPLICATE VALUES ARE ACCEPTED
        temp1->element1=temp->element1;
        temp2->element1=temp->element3;
        temp->element1=temp->element2;
        temp->element1=-1;
        temp->element3=-1;
        temp1->element1=-1;
        temp1->element3=-1;
        temp2->element1=-1;
        temp2->element3=-1;
        temp->left=temp1;
        temp->right=temp2;

    }
    else//when this is not the first node then we will get three nodes whenever child node splits
    {
       if(temp->parent->left!=NULL&&temp->right!=NULL)//we need to create the middle node
       {
        node *temp1=new node;

        int t2=temp->element3;

        temp1->parent=temp->parent;//linking
        temp1->left=NULL;
        temp1->right=NULL;
        temp1->middle=NULL;
        temp1->element1=t2;
        temp1->element2=-1;
        temp1->element3=-1;
        temp->element3=-1;
        temp->parent->middle=temp1;//linking
        temp->parent->left=temp;//linking



       }
       else
       {
        node *temp1=new node;

        int t2=temp->element3;

        temp1->parent=temp->parent;//linking
        temp1->left=NULL;
        temp1->right=NULL;
        temp1->middle=NULL;
        temp1->element1=t2;
        temp1->element2=-1;
        temp1->element3=-1;
        temp->element3=-1;
        temp->parent->right=temp1;//linking
        temp->parent->left=temp;//linking


       }
     int t=temp->element2;
     temp->element2=-1;
    insert(temp->parent,t); //here parent is not null so we have to send the item upwards
    }
}

node* node::insert(node *root,int item)
{
    cout<<"\n inside the function \n";
node *temp=new node;
temp->parent=NULL;
temp->left=NULL;
temp->right=NULL;
temp->middle=NULL;
cout<<"\n all are initialised \n";
//if no node exist
 if(root==NULL)
 {
     cout<<"\n  Value inserted \n";
 temp->element1=item;
 return temp;
 }

temp=search(root,item);
//when the node has only one node filled
 if(temp->element1!=-1&&temp->element2==-1)
 {
 if(temp->element1<item)
 temp->element2=item;
 else
   {
   int t=temp->element1;
   temp->element1=item;
   temp->element2=t;//for sorting the 2 values
   }
 }
 else if(temp->element1!=-1&&temp->element2!=-1)
 {
    if(item>temp->element1&&item<temp->element2)
    {
    temp->element3=temp->element2;
    temp->element2=item;
    }
    else if(item<temp->element1)
    {
    temp->element3=temp->element2;
    temp->element2=temp->element1;
    temp->element1=item;
    }
    else if(item>temp->element2)
    temp->element3=item;


//now calling the balance function

    balance(temp);
 }//end of else if

return temp;
}//end of funciton

//to search the node where we have to insert
node* node::search(node*root,int item)
{
node *temp=new node;
temp=root;
cout<<"\n inside the search function \n";
    while(temp!=NULL)
    {
      if(temp->element1>item)
      temp=temp->left;
      else if(temp->element1<item)
      {
          if(temp->element2!=-1)
          {
              if(temp->element2>item)
              temp=temp->middle;
              else
              temp=temp->right;
          }
      }

    } //end while
return temp;//this is the node where value has to be inserted

}
//display
void node::preorder(node *root){
    if(root==NULL){
        return;
    }
    cout<<root->element1;
    if(root->element2!=-1)
        cout<<root->element2;
    preorder(root->left);
        preorder(root->right);
        preorder(root->middle);


}


int main(){
    int n,ch;
node *root=new node,*head=new node;
root=NULL,head=NULL;
node object;
    while(1){
        cout<<"\n1.INSERT \n2.DISPLAY \n3.EXIT\n";
        cout<<"Enter Choice: ";
            cin>>ch;

        switch(ch){
        case 1:{
            cout<<"\nEnter the element you want to insert \n";
            cin>>n;
            root=object.insert(root,n);
            cout<<"\n function called \n";
            if(head==NULL)
            head=root;
            break;
        }
        case 2:{
            object.preorder(head);
            break;
        }
        case 3: break;
        }
    }

return 0;
}