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).




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.


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.

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