Convert Binary Tree to Doubly Linked List
Convert a given binary tree to a doubly-linked list.
We'll cover the following...
Statement
Convert a given binary tree to a doubly-linked list, such that the order of the doubly-linked list is the same as the in-order traversal of the binary tree.
After conversion, the left pointer of the node should point to the previous node in the doubly linked list, and the right pointer should point to the next node in the doubly linked list. The head node of the linked list must be the first node in the in-order traversal of the original binary tree.
Example
Consider the binary tree below:
Its in-order traversal will be 25, 30, 50, 60, 75, 100, 125, 200, 350. So, the output doubly linked list will look like:
Sample Input
The input list below represents the level-order traversal of the binary tree:
[100, 50, 200, 25, 75, 125, 350, 30, 60]
Expected output
The linked list below represents the in-order traversal of the binary tree:
25 <--> 30 <--> 50 <--> 60 <--> 75 <--> 100 <--> 125 <--> 200 <--> 350
Try it yourself
Note: The binary tree node’s class has members
left
andright
to store references to other nodes, along with the memberdata
to hold the node’s value.
#include <iostream>#include <string>#include <vector>#include "BinaryTree.cpp"class ToDLL{public:static BinaryTreeNode* ConvertToLinkedList(BinaryTreeNode* root){// TODO: Write - Your - Codereturn root;}};
Solution
We will perform the conversion in place instead of creating a separate linked list, so we will modify the nodes in the binary tree ...