Binary Trees: Convert Binary Tree to DLL

Problem Statement:

You are given a binary tree, you need to convert into DLL.

Example

In-place convert Binary Tee to a Doubly Linked List

4 <-> 5 <-> 14 <-> 10 <-> 15 <-> 20 <-> 30

Solution

In this solution we use in-order traversal of the tree.

We perform below steps:

Insert every node at the beginning of DLL.

Then reverse the LL to get the node as in the in-order traversal.

So instead of that, we can do a reverse in-order traversal.

i.e visit right child and then left child.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};

void convert_to_dll(Node* root, Node*& head) 
{ 
    if (root == NULL) 
        return; 
  
    //  convert right subtree recursively
    convert_to_dll(root->right, head); 
  
    // insert root into DLL 
    root->right = head; 
  
    // change the left pointer of previous head 
    if (head != NULL) 
        head->left = root; 
  
    // change head of DLL
    head = root; 
  
    // convert left subtree recursively
    convert_to_dll(root->left, head); 
} 
  

void print_dll(Node *node)
{
    while (node!=NULL)
    {
        cout << node->data << " ";
        node = node->right;
    }
}

int main()  
{  
    Node* root = nullptr;

    root = new Node(10);
    root->left = new Node(12);
    root->right = new Node(25);
    root->left->left = new Node(25);
    root->left->right = new Node(30);
    root->right->left = new Node(35);

    Node *head = nullptr;

    convert_to_dll (root, head);

    cout<<"DLL is = "<<endl;
    print_dll(head);



    return 0;  
}  

Output:

DLL is =
25 12 30 10 35 25