Convert a given Binary Tree to Doubly Linked List (Set 2) in C++

In this tutorial, we will be discussing a program to convert a binary tree to a doubly linked list.

For this we will be provided with a binary tree. Our task is to convert it into a doubly linked list such that the left and right pointers become the previous and next pointers. Also the sequential order of the doubly linked list must be equal to the inorder traversal of the binary tree.

For this we are having a different approach. We will be traversing the binary tree in reverse inorder way. Along with we will be creating new nodes and moving the head pointer to the latest one; this will create the doubly linked list from the end to the start.

Example

 Live Demo

#include <stdio.h> #include <stdlib.h> //node structure for tree struct Node{    int data;    Node *left, *right; }; //converting the binary tree to //doubly linked list void binary_todll(Node* root, Node** head_ref){    if (root == NULL)       return;    //converting right subtree    binary_todll(root->right, head_ref);    //inserting the root value to the    //doubly linked list    root->right = *head_ref;    //moving the head pointer    if (*head_ref != NULL)       (*head_ref)->left = root;    *head_ref = root;    //converting left subtree    binary_todll(root->left, head_ref); } //allocating new node for doubly linked list Node* newNode(int data){    Node* node = new Node;    node->data = data;    node->left = node->right = NULL;       return node; } //printing doubly linked list void print_dll(Node* head){    printf("Doubly Linked list:\n");    while (head) {       printf("%d ", head->data);       head = head->right;    } } int main(){    Node* root = newNode(5);    root->left = newNode(3);    root->right = newNode(6);    root->left->left = newNode(1);    root->left->right = newNode(4);    root->right->right = newNode(8);    root->left->left->left = newNode(0);    root->left->left->right = newNode(2);    root->right->right->left = newNode(7);    root->right->right->right = newNode(9);    Node* head = NULL;    binary_todll(root, &head);    print_dll(head);    return 0; }

Output

Doubly Linked list: 0 1 2 3 4 5 6 7 8 9