#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *left;
node *right;
node();
node(int data){
this->data = data;
this->left = this->right = NULL;
}
};
//**head act as a pointer to pointer
void bsttodll(node *root,node **head){
if(root == NULL)return;
//Mention static as to access it through all recursion calls
static node *prev = NULL;
//We have to traverse recursively in left sub tree
bsttodll(root->left,head);
//When it'll reach the lestmost node and if prev == null then set head as root and prev = root
//After this recursion it'll back to the previous recursion step and check prev, and set
if(prev == NULL) *head = root;
//Here root->left store the prev and prev->right will store the root address
else{
root->left = prev;
prev->right = root;
}
prev = root;
bsttodll(root->right,head);
}
void preorder(node *root){
if(root==NULL)return;
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
void printdll(node *head){
while(head != NULL){
cout<<head->data<<" ";
head = head->right;
}
}
int main()
{
node *root = new node(22);
root->left = new node(7);
root->right = new node(28);
root->left->left = new node(4);
root->left->right = new node(9);
root->right->left = new node(26);
root->right->right = new node(29);
preorder(root);
cout<<endl;
node *head = NULL;
bsttodll(root,&head); //give address of dll node as head
printdll(head);
return 0;
}
Output:
22 7 4 9 28 26 29
4 7 9 22 26 28 29
Top comments (0)