Binary2DoublyLinkedList.cpp

// A C++ program for in-place conversion of Binary Tree to DLL
#include <iostream>
using namespace std;
 
/* A binary tree node has data, and left and right pointers */
struct node
{
    int data;
    node* left;
    node* right;
};


node* BinaryTree2DLL(node* root) {
    if (root->left == NULL && root->right==NULL){
        return root;
    }

    node* a = BinaryTree2DLL(root->left);

    root->left = a;
    if (a) a->right = root;

    node* b = BinaryTree2DLL(root->right);
    root->right = b;
    if (b) b->left = root;
    return a;
}
 
// A simple recursive function to convert a given Binary tree to Doubly
// Linked List
// root --> Root of Binary Tree
// head --> Pointer to head node of created doubly linked list
void BinaryTree2DoubleLinkedList(node *root, node **head)
{
    // Base case
    if (root == NULL) return;
 
    // Initialize previously visited node as NULL. This is
    // static so that the same value is accessible in all recursive
    // calls
    static node* prev = NULL;
 
    // Recursively convert left subtree
    BinaryTree2DoubleLinkedList(root->left, head);
 
    // Now convert this node
    if (prev == NULL)
        *head = root;
    else
    {
        root->left = prev;
        prev->right = root;
    }
    prev = root;
 
    // Finally convert right subtree
    BinaryTree2DoubleLinkedList(root->right, head);
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* new_node = new node;
    new_node->data = data;
    new_node->left = new_node->right = NULL;
    return (new_node);
}
 
/* Function to print nodes in a given doubly linked list */
void printList(node *node)
{
    cout<<"Sorted List "<<endl;
    while (node!=NULL)
    {
        cout << node->data << " ";
        node = node->right;
    }
}
 
/* Driver program to test above functions*/
int main()
{
    // Let us create the tree shown in above diagram
    node *root        = newNode(10);
    root->left        = newNode(12);
    root->right       = newNode(15);
    root->left->left  = newNode(25);
    root->left->right = newNode(30);
    root->right->left = newNode(36);
 
    // Convert to DLL
    //node *head = NULL;
    //BinaryTree2DoubleLinkedList(root, &head);
 
    // Print the converted list
    //printList(head);
 
    node* head1 = BinaryTree2DLL(root);
    printList(head1);
    return 0;
}