DEV Community

Soham
Soham

Posted on

BST To Doubly Linked List Conversion Using C++

#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;
}

Enter fullscreen mode Exit fullscreen mode

Output:

22 7 4 9 28 26 29
4 7 9 22 26 28 29

Top comments (0)