Flattening the Tree into Double linked list

Problem

Given the binary tree as shown below:

Figure 1. Binary Tree

Convert the tree into a double-linked list, where the left pointer and right pointer become the prev and next pointer respectively.

Your algorithm should produce the double-linked list as below:

ANSWER

Given the binary tree, we first need to traverse values in the nodes in ascending order within the tree.

We can use the In-order search strategy to traverse the tree in ascending order. The following is the algorithm.

Inorder_tranverse(node *cur)
{
     if (!cur)
        return;
     Inorder_tranverse(cur->left);
 
     // We need to do something here 
     
     Inorder_tranverse(cur->right);
}

Now, we have the strategy to traverse in the correct order, What is left is to find the way to build the double-linked list. To achieve this we would need two external pointers: head, tail to remember the start of the linked list and the end of the linked list.

Basically, given the current node, we do the followings:

1) if head is empty, assign current node to head and tail then exit.

2) if the head is not empty,  let  tail->right point to the current node
3) let  cur->left  point to tail
4) move the tail pointer to cur

The construction of the linked list will finish as soon as the in-order traversal is one, thereby giving the running time of O(N), where N is the # of nodes in the tree.

Here is the complete code running in O(N).

	#include <iostream>
	using namespace std;
	struct node {
	node* left;
	node* right;
	int value;
	node(int v): value(v), left(0), right(0){}
	};
	node * head = 0;
	node * tail = 0;
	void flatten_tree(node * cur)
	{
	if (!cur)
	return;
	flatten_tree(cur->left);
	if (!head)
	{
	head = tail = cur;
	} else {
	tail->right = cur;
	cur->left = tail;
	tail = cur;
	}
	flatten_tree(cur->right);
	}
	int main()
	{
	node * n1 = new node(1);
	node * n2 = new node(2);
	node * n3 = new node(3);
	node * n4 = new node(4);
	node * n5 = new node(5);
	node * n6 = new node(6);
	node * n7 = new node(7);
	node * n8 = new node(8);
	node * n9 = new node(9);
	n6->left = n2;
	n6->right = n8;
	n2->left = n1;
	n2->right = n3;
	n8->left = n7;
	n8->right = n9;
	flatten_tree(n6);
	node * cur = head;
	node * prev = 0;
	while(cur)
	{
	if (cur->left == prev)
	cout<<"<- ";
	cout<<cur->value<<" ->";
	prev = cur;
	cur = cur->right;
	}
	return 1;
	}

view raw flatten_tree.cpp hosted with ❤ by GitHub

Practice statistics

14:28 mins: to write up the algorithm
05:04 mins: to verify the code


UPDATE(2019-07-28): solved the problem using in-order search and global pointers, head, and prev.

Took too long to fix the bug in additional print logic for "<->". I was assigning prev incorrectly in the print logic. In the real interview, don't bother adding it.

	class Node:
	def __init__(self, value):
	self.value = value
	self.left = self.right = None
	class FlattenTree:
	def flatten(self, root):
	self.head = None
	self.prev = None
	self.inorder_search(root)
	# print values starting from head
	prev = None
	current = self.head
	while current != None:
	if (prev != None and prev.right == current and current.left == prev):
	print ("<->"),
	print ("{} ".format(current.value)),
	prev = current
	current = current.right
	def inorder_search(self, current):
	if current == None:
	return
	self.inorder_search(current.left)
	# connct prev and current
	if self.prev == None:
	self.head = current
	else:
	self.prev.right = current
	current.left = self.prev
	#set prev to current node
	self.prev = current
	self.inorder_search(current.right)
	flattener = FlattenTree()
	# test code
	n2 = Node(2)
	n3 = Node(3)
	n4 = Node(4)
	n5 = Node(5)
	n6 = Node(6)
	n7 = Node(7)
	n8 = Node(8)
	n5.left = n3
	n5.right = n7
	n3.left = n2
	n3.right = n4
	n7.left = n6
	n7.right = n8
	print ("flattened tree:")
	flattener.flatten(n5)

view raw amazon_flatten_tree.py hosted with ❤ by GitHub

Practice statistics

6:00: algorithm
11:33: to write the code
05:20: to review the code and fix the code (check the answer correctly.)

13:53: to fix the additional printing method. In the real interview, I won't bother to print this arrow.

        There was a bug in that logic assigning prev after the current is updated.

UPDATE(2022-06-11): solved again in python. make one silly mistake in the test input.

	# code
	class Node:
	def __init__(self, value):
	self.value = value
	self.left = None
	self.right = None
	class LinkedNode:
	def __init__(self, value):
	self.value = value
	self.prev = None
	self.next = None
	class FlattenTree:
	def __init__(self):
	self.first = None
	self.cur = None
	def flatten(self, node):
	if node is None:
	return
	# fatten left side of the tree
	self.flatten(node.left)
	# add the current node to the linked list
	if self.first is None:
	self.first = LinkedNode(node.value)
	self.cur = self.first
	else:
	next_node = LinkedNode(node.value)
	self.cur.next = next_node
	next_node.prev = self.cur
	self.cur = next_node
	# flatten right side of the tree
	self.flatten(node.right)
	# test
	c9 = Node(9)
	c5 = Node(5)
	c10 = Node(10)
	c9.left = c5
	c9.right = c10
	c3 = Node(3)
	c6 = Node(6)
	c5.left = c3
	c5.right = c6
	c11 = Node(11)
	c10.right = c11
	c2 = Node(2)
	c4 = Node(4)
	c3.left = c2
	c3.right = c4
	c7 = Node(7)
	c6.right = c7
	c12 = Node(12)
	c11.right = c12
	root = c9
	flattener = FlattenTree()
	flattener.flatten(root)
	list_head = flattener.first
	cur = list_head
	while cur != None:
	print("{} <->".format(cur.value))
	cur = cur.next
	print ("NIL")

view raw flatten_bst_to_list.py hosted with ❤ by GitHub

07:00: for working algorithm

16:00: coding with the bug in the test input tree (accidentally recursive tree)

06:00: to fix the bug in the input tree