Problem Statement:
You are given a binary tree, you need to convert into DLL.
Example
In-place convert Binary Tee to a Doubly Linked List 4 <-> 5 <-> 14 <-> 10 <-> 15 <-> 20 <-> 30
Solution
In this solution we use in-order traversal of the tree.
We perform below steps:
Insert every node at the beginning of DLL.
Then reverse the LL to get the node as in the in-order traversal.
So instead of that, we can do a reverse in-order traversal.
i.e visit right child and then left child.
Solution in C++
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <queue> #include <vector> #include <stack> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; void convert_to_dll(Node* root, Node*& head) { if (root == NULL) return; // convert right subtree recursively convert_to_dll(root->right, head); // insert root into DLL root->right = head; // change the left pointer of previous head if (head != NULL) head->left = root; // change head of DLL head = root; // convert left subtree recursively convert_to_dll(root->left, head); } void print_dll(Node *node) { while (node!=NULL) { cout << node->data << " "; node = node->right; } } int main() { Node* root = nullptr; root = new Node(10); root->left = new Node(12); root->right = new Node(25); root->left->left = new Node(25); root->left->right = new Node(30); root->right->left = new Node(35); Node *head = nullptr; convert_to_dll (root, head); cout<<"DLL is = "<<endl; print_dll(head); return 0; }
Output:
DLL is = 25 12 30 10 35 25