Coderust: Hacking the Coding Interview/

...

/

Convert Binary Tree to Doubly Linked List

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:

G 100 100 50 50 100->50 200 200 100->200 25 25 50->25 75 75 50->75 125 125 200->125 350 350 200->350 invis2 30 25->invis2 60 60 75->60

Its in-order traversal will be 25, 30, 50, 60, 75, 100, 125, 200, 350. So, the output doubly linked list will look like:

G 25 25 30 30 25->30 50 50 30->50 60 60 50->60 75 75 60->75 100 100 75->100 125 125 100->125 200 200 125->200 350 350 200->350

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 and right to store references to other nodes, along with the member data to hold the node’s value.

main.cpp
BinaryTree.cpp
BinaryTreeNode.cpp
#include <iostream>
#include <string>
#include <vector>
#include "BinaryTree.cpp"
class ToDLL{
public:
	static BinaryTreeNode* ConvertToLinkedList(BinaryTreeNode* root){
		// TODO: Write - Your - Code
		return 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 ...