1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL)
| #include<iostream> | |
| #include<queue> | |
| #include<map> | |
| #include<climits> | |
| #include<stack> | |
| #include<stdio.h> | |
| using namespace std; | |
| struct node{ | |
| int data; | |
| struct node* left; | |
| struct node* right; | |
| }; | |
| struct node* newNode(int data){ | |
| struct node* node=new(struct node); | |
| node->data=data; | |
| node->left=node->right=NULL; | |
| return node; | |
| } | |
| struct node* insert(struct node* node,int data){ | |
| if(node==NULL) | |
| return (newNode(data)); | |
| if(data<=node->data) | |
| node->left=insert(node->left,data); | |
| else | |
| node->right=insert(node->right,data); | |
| return node; | |
| } | |
| node* binToList(node* root){ | |
| if(root==NULL) | |
| return root; | |
| if(root->left!=NULL){ | |
| node* left; | |
| left=binToList(root->left); | |
| for(;left->right!=NULL;left=left->right); | |
| left->right=root; | |
| root->left=left; | |
| } | |
| if(root->right!=NULL){ | |
| node* right; | |
| right=binToList(root->right); | |
| for(;right->left!=NULL;right=right->left); | |
| root->right=right; | |
| right->left=root; | |
| } | |
| return root; | |
| } | |
| node* convertToDLL(node* root){ | |
| if(root==NULL) | |
| return root; | |
| root=binToList(root); | |
| for(;root->left!=NULL;root=root->left); | |
| return root; | |
| } | |
| int main(){ | |
| struct node* root=NULL; | |
| root=insert(root,4); | |
| root=insert(root,2); | |
| root=insert(root,5); | |
| root=insert(root,1); | |
| root=insert(root,3); | |
| node* list=convertToDLL(root); | |
| for(;list!=NULL;list=list->right) | |
| cout<<list->data<<" "; | |
| } |
Thanks to geeksforgeeks for providing such an awesome approach
coding hangover 