program to convert a given binary tree to doubly linked list.














































program to convert a given binary tree to doubly linked list.



Description:


Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.


1. If left subtree exists, process the left subtree

1  .a) Recursively convert the left subtree to DLL.

     b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).

     c) Make inorder predecessor as previous of root and root as next of inorder predecessor.

2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).

   a) Recursively convert the right subtree to DLL.

   b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).

   c) Make inorder successor as next of root and root as previous of inorder successor.

3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).


Here's the code in C++ which convert a given binary tree to doubly linked list:



Code:




#include <iostream>
using namespace std;


struct Node
{

int data;
Node *left, *right;

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


void printDLL(Node* &head)
{
Node* curr = head;
while (curr != nullptr)
{
cout << curr->data << " ";
curr = curr->right;
}
}


void convert(Node* root, Node* &head)
{

if (root == nullptr)
return;


convert(root->left, head);


Node* right = root->right;


root->right = head;
if (head != nullptr)
head->left = root;

head = root;


convert(right, head);
}


void reverse(Node*& head)
{
Node* prev = nullptr;
Node* current = head;

while (current)
{
swap(current->left, current->right);
prev = current;
current = current->left;
}

if (prev != nullptr)
head = prev;
}


void convert(Node* root)
{

Node* head = nullptr;


convert(root, head);


reverse(head);


cout<<"The DLL are:";
printDLL(head);
}


int main()
{

int a,b,c,d,e,f,g;
cout<<"Conversion of Binary tree to DLL\n";
cout<<"Enter 7 binary tree nodes:\n";
cin>>a>>b>>c>>d>>e>>f>>g;
Node* root = new Node(a);
root->left = new Node(b);
root->right = new Node(c);
root->left->left = new Node(d);
root->left->right = new Node(e);
root->right->left = new Node(f);
root->right->right = new Node(g);

convert(root);

return 0;
}


Output:



1


2

3


Conversion of Binary tree to DLL


Enter 7 binary tree nodes:5 6 7 8 9 10 11


The DLL are:8 6 9 5 10 7 11






More Articles of DINESH GOUDA:

Name Views Likes
C++ boost::rational 154 1
program to convert a given binary tree to doubly linked list. 220 4

Comments