WE'll be taking inorder traversal of the tree and during the traversal will modify the right pointers only(using method "make_right") such that a linked list is formed having only valid right pointers. Then another method "make_left" is called to make the left pointers of the nodes point to valid previous nodes.

#include<iostream.h>

class node
{
    protected:
        int info;
        node* left;
        node* right;
    public:

        void insert(node ** root,int n)
        {
            if((*root) == NULL)
            {
                (* root)=new node;
                (* root)->info=n;
                (* root)->left=NULL;
                (* root)->right=NULL;
            }
            else
            {
                node * ptr=(* root);
                while(1)
                {
                    if(n > ptr->info && ptr->right!=NULL)
                        ptr=ptr->right;
                    else if(n > ptr->info && ptr->right==NULL)
                    {
                        ptr->right=new node;
                        ptr=ptr->right;
                     // cout<<"RIGHT";
                        ptr->info=n;
                        ptr->left=NULL;
                        ptr->right=NULL;
                        break;
                    }
                    else if(n <= ptr->info && ptr->left!=NULL)
                        ptr=ptr->left;
                    else
                    {
                        ptr->left=new node;
                        ptr=ptr->left;
                        //  cout<<"left";
                        ptr->info=n;
                        ptr->left=NULL;
                        ptr->right=NULL;
                        break;
                    }
                }
            }
        }

        void inorder(node * ptr)
        {
            if(ptr->left!=NULL)
                inorder(ptr->left);
            cout<<"\n--"<<ptr->info;
            if(ptr->right!=NULL)
                inorder(ptr->right);
        }

        void make_right(node* root,node **start)
        {
            if(root== NULL)
                return;

            make_right(root->left,start);

            (*start)->right=root;
            (*start)=root;

            make_right(root->right,start);
        }

        node* make_left(node* root)
        {
            if(root==NULL)
                return NULL;
            node *ptr=root;
            while((ptr->right) != NULL)
            {
                ptr->right->left=ptr;
                ptr=ptr->right;
            }
            root->left=NULL;
            return (ptr);
        }

        void make_dll(node *root,node **start,node **end)
        {
            if(root==NULL)
            {
                (*end)=NULL;
                return;
            }

            (*start)=new node;
            node *st=(*start);
            make_right(root,start);     
            (*start)=st->right;
            (*end)=make_left(*start);
        }


        void print_list(node *st)
        {
            cout<<"\n\n";
            while(st!=NULL)
            {
                cout<<st->info<<" --> ";
                st=st->right;
            }

        }

        void print_rev_list(node *st)
        {
            cout<<"\n\n";
            while(st!=NULL)
            {
                cout<<st->info<<" --> ";
                st=st->left;
            }

        }

};

int main()
{
    node *root=NULL;
    root->insert(&root,5);
    root->insert(&root,8);
    root->insert(&root,6);
    root->insert(&root,3);
    root->insert(&root,2);
    root->insert(&root,4);
    root->insert(&root,7);
    root->insert(&root,9);
    root->inorder(root);

    node* end;
    node*start;
    root->make_dll(root,&start,&end);
    root->print_list(start);
    root->print_rev_list(end);
    return 0;
}

Edited 3 Years Ago by pankaj.leon: updations

Click Here

your code matched with the code given here. It seems you are clear with the algo, but some issues are there which are hard to find by just looking at your code. I have given you link which you will find useful as it explains this concept very greatly. hope it helps! thanks.

This article has been dead for over six months. Start a new discussion instead.