How To Create Right Threaded Binary Search Tree(Recursive)?

 

#include<iostream>

#include<conio.h>

#include<stdlib.h>

using namespace std;

struct node

{

    int data;

    node *left,*right;

    bool rightThread;

    node(int data)

    {

        this->data=data;

        left=right=NULL;

        rightThread=false;

    }

};

node* insert_data(node *root,int data)

{

    if(root==NULL)

    {

        root=new node(data);

    }

    else if(data<=root->data)

    {

        root->left=insert_data(root->left,data);

        if(root->left->right==NULL)

        {

            root->left->right=root;

            root->left->rightThread=true;

        }

    }

    else if(data>root->data)

    {

        if(root->rightThread==true)

        {

            node *temp=new node(data);

            temp->right=root->right;

            root->right=temp;

            root->rightThread=false;

            temp->rightThread=true;

        }

        else

            root->right=insert_data(root->right,data);

    }

    return root;

}

void inorder_traversal(node *root)

{

    if(root==NULL)

        return;

    while(root->left!=NULL)

        root=root->left;

    while(root!=NULL)

    {

        cout<<root->data<<" ";

        if(root->rightThread==true)

            root=root->right;

        else

        {

            root=root->right;

            if(root!=NULL)

            {

                while(root->left!=NULL)

                    root=root->left;

            }

        }

    }

}

int main()

{

    node *root=NULL;

    int ch,data;

    while(1)

    {

        cout<<endl<<"Enter 1.To Insert Element In Tree."<<endl;

        cout<<"Enter 2.For In-order Traversal Of Tree."<<endl;

        cout<<"Enter 3.to exit."<<endl;

        cin>>ch;

        switch(ch)

        {

        case 1:cout<<"Enter Data."<<endl;

               cin>>data;

               root=insert_data(root,data);

               break;

        case 2:cout<<endl<<"In-order Traversal:";

               inorder_traversal(root);

               break;

        case 3:exit(0);

        default:cout<<"Invalid Choice."<<endl;

        }

    }

}