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














































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



//C++ program to convert a given binary tree to doubly linked list /* Description:
To convert the given binary tree to a doubly-linked list we will use the left and right pointers
of tree node as previous and next pointer in a doubly linked list.
we will use recursion with inorder traversal of tree.
*/
#include<iostream> using namespace std;

//user defined data type for node struct TreeNode { int data; TreeNode *left,*right; }; //recursive approach for conversion //root refers to the root of the binary tree //head refers to the head of doubly linked list void binaryTree2DoublyList(TreeNode* root, TreeNode** list_head) { //base case if(root==NULL) return; //Initialise last visited node as NULL static TreeNode* prev=NULL; //static makes the value same for all the recursion calls //recursively converting left subtree binaryTree2DoublyList(root->left,list_head); //converting the current node if(prev==NULL) *list_head=root; else { root->left=prev; prev->right=root; } prev=root; /* after completing the left subtree we finally go to right subtree*/ binaryTree2DoublyList(root->right,list_head); } //return type is of tree node type as it will pointer to the new node TreeNode* getNode(int value) { TreeNode* temp=new TreeNode; temp->data=value; temp->left=temp->right=NULL; return temp; } //function to print the converted list void print(TreeNode* head) { cout<<"Converted list :\n"; while(head) { cout<<head->data<<" "; head=head->right; } } int main() { //a null pointer which will contain head of linked list TreeNode* head=NULL; //creating the binary tree TreeNode* root=getNode(10); root->left=getNode(20); root->right=getNode(15); root->left->left=getNode(17); root->left->right=getNode(34); root->right->left=getNode(12); root->right->right=getNode(11); binaryTree2DoublyList(root,&head);//calling conversion function print(head);//printing the data elements of list return 0; }


OUTPUT








More Articles of Akash Shukla:

Name Views Likes
C++ program to convert a given binary tree to doubly linked list 113 0

Comments