Binary Tree to CDLL Geeks solution

Binary Tree to CDLL Geeks solution

  July 23, 2017    

---

First read this problem :
https://hackerranksolutionc.blogspot.com/2017/07/binary-tree-to-dll-geeks-solution.html

Problem :

Given a Binary Tree (BT), convert it to a Circular Doubly Linked List(DLL) In-Place

Idea:

Use concept of previous problem (link given above), loop to leftmost and rightmost node and connect them .

Code:

/*Complete the function below
Node is as follows:
struct Node
{
    struct Node *left, *right;
    int data;
};*/
Node *BtoDLL(Node *root)
    {
        //if tree is empty
 if(root==NULL)
 return root;
 if(root->left!=NULL)
 {
     Node *x=BtoDLL(root->left);
//go to last right node 
     for(;x->right;x=x->right);
     x->right=root;
     root->left=x;
 }
 if(root->right!=NULL)
 {
     Node *y=BtoDLL(root->right);
     for(;y->left;y=y->left);
     y->left=root;
     root->right=y;
 }
 return root;
    }
Node *bTreeToCList(Node *root)
{
if(root==NULL)
 return root;
 Node *head=BtoDLL(root);
 Node *temp=head;
 while(temp->right!=NULL)
 temp=temp->right;
 while(head->left!=NULL)
 head=head->left;
 temp->right=head;
 head->left=temp;
 return head;
}