Convert a given binary Tree to Doubly Linked List (DLL) using C++ program

Binary Tree to Doubly Linked List Conversion: In this tutorial, we will learn how to convert a given binary tree to a doubly linked list (DLL) using the C++ program? By Souvik Saha Last updated : August 02, 2023

Problem statement

Given a binary tree, and we have to write a C++ program to convert it to a doubly linked list (DLL).

Algorithm

The following are the steps/algorithm to convert a binary tree to doubly linked list:

We start to convert the tree node to DLL from the rightmost tree node to the leftmost tree node.
Every time we connect the right pointer of a node to the head of the DLL.
Connect the left pointer of the DLL to that node.
Make that node to the head of the linked list.
Repeat the process from right to left most node of the tree.

C++ program to convert a given binary tree to doubly linked list

#include <bits/stdc++.h>
using namespace std;

struct node {
    int data;
    node* left;
    node* right;
};

//Create a new node
struct node* create_node(int x)
{
    struct node* temp = new node;
    temp->data = x;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

//convert a BST to a DLL
void BinarytoDll(node* root, node** head)
{
    if (root == NULL)
        return;
    BinarytoDll(root->right, head);
    root->right = *head;
    if (*head != NULL) {
        (*head)->left = root;
    }
    *head = root;
    BinarytoDll(root->left, head);
}

//Print the list
void print(node* head)
{
    struct node* temp = head;
    while (temp) {
        cout << temp->data << " ";
        temp = temp->right;
    }
}

//print the tree in inorder traversal
void print_tree(node* root)
{
    if (root == NULL) {
        return;
    }
    print_tree(root->left);
    cout << root->data << " ";
    print_tree(root->right);
}

int main()
{
    struct node* root = create_node(5);
    root->left = create_node(6);
    root->right = create_node(7);
    root->left->left = create_node(8);
    root->left->right = create_node(1);
    root->right->right = create_node(0);
    cout << "Print Tree" << endl;
    print_tree(root);
    struct node* head = NULL;
    BinarytoDll(root, &head);
    cout << "\nDoubly Linked List" << endl;
    print(head);

    return 0;
}

Output

Print Tree
8 6 1 5 7 0
Doubly Linked List
8 6 1 5 7 0