Convert a given binary Tree to Doubly Linked List

Convert a given binary Tree to Doubly Linked List

In this example, we will see a C++ program through which we can convert a given binary tree to a doubly linked list.

• STEP 1: We start to convert the tree node to DLL from the rightmost tree node to the leftmost tree node.
• STEP 2: Every time we connect the right pointer of a node to the head of the DLL.
• STEP 3: Connect the left pointer of the DLL to that node.
• STEP 4: Make that node to the head of the linked list.
• STEP 5: Repeat the process from right to left most node of the tree.

Example

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