Convert A Binary Tree To A Circular Doubly Linked List

Hard
0/120
Average time to solve is 10m
profile
Contributed by
7 upvotes
Asked in company
IBM

Problem statement

Given a binary tree, convert it into a Circular Doubly Linked List.

Linked List must follow these conditions: 
Left and right pointers in nodes to be used for previous and next pointers in the Circular LinkedList.

The order of nodes must be the same as the in-order traversal of the binary tree.

The first node of the in-order traversal must be the head of the Circular Doubly Linked List.

Returned Circular Doubly Linked List must be an in-placed changed Circular Doubly Linked List, you are not allowed to use any extra space to create a Circular Doubly Linked List.
Example: 
In the below binary tree

alt text

The inorder traversal of this binary tree 
4 => 2 => 5 => 1 => 3 => 6

Hence we return the head of this Circular Doubly Linked List.

alt text

Note: 
You are not required to print the output explicitly, it has already been taken care of. Just implement the function and return the head of the Circular Doubly Linked List.

The ‘left’ pointer must point to the previous node and the ‘right’ pointer must point to the next node.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines represent the ‘T’ test cases.

The first line of input contains the elements of the tree in the level order form separated by a single space.

If any node does not have a left or right child, take -1 in its place. Refer to the example below.

Example:

Elements are in the level order form. The input consists of values of nodes separated by a single space in a single line. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

alt text

 1
 2 3
 4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1

Explanation :
Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 2
Right child of 1 = 3

Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)

Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.

The input ends when all nodes at the last level are null (-1).
Note : 
The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format: 
For every test case, return the head of the Circular Doubly Linked List.
Constraint : 
1 <= T <= 100
1 <= N <= 3000
-10^9 <= data <= 10^9

Time Limit: 1 second
Sample Input 1:
2
1 2 3 -1 -1 4 5 -1 -1 -1 -1
1 2 3 -1 -1 -1 2 -1 -1
Sample Output 1:
2 1 4 3 5 
2 1 3 2
Explanation For Sample Output 1:
Test case 1:

alt text

The inorder traversal of this binary tree 
2 => 1 => 4 => 3 => 5

Hence we return the head ( 2 ) of this type of Circular Doubly Linked List.

alt text

Test case 2:

alt text

The inorder traversal of this binary tree 
2 => 1 => 3 => 2

Hence we return the head ( 2 ) of this type of Circular Doubly Linked List.

alt text

Sample Input 2:
2
1 2 -1 3 -1 4 -1 -1 -1
1 2 3 4 -1 -1 5 -1 -1 -1 -1
Sample Output 2:
4 3 2 1
4 2 1 3 5
Hint

Can we use the Divide and Conquer approach?

Approaches (1)
Recursion

In the in-order traversal. first, traverse the left subtree, then the root, and in the end traverse the right subtree. So try to convert the left and right subtree in doubly linked list and concatenate both subparts with the current node.

 

  • Recursively convert left subtree in a Circular Doubly Linked List and call it ‘leftDLL’.
  • Recursively convert the right subtree in a Circular Doubly Linked List and call it ‘rightDLL’.
  • Convert current node to Circular Doubly Linked List, so point the left and right pointer to itself
    • currrentNode->left = currentNode
    • currentNode->right = currentNode
  • Concatenate the left part Circular Doubly Linked List ‘leftDLL’ to the current node. Two types of combination are possible -
    • If ‘leftDLL’ is ‘null/None’ then
      • Return only ‘currentNode’
    • If ‘leftDLL’  exists:
      • Then convert ‘leftDLL’ and ‘currentNode’ in a single Circular Doubly Linked List, return ‘leftDLL’ as the head of new Circular DLL.
      • Refer figure ( LEFT DLL + CURRENT NODE )
      • To concatenate these two parts we first find the last node of  ‘leftDLL’ with ‘leftLast = leftDLL->left’ because, in a circular doubly linked list, the last node can be pointed by the previous pointer of the head node.
      • Then we can simply connect the last node ‘leftLast’ of ‘leftDLL’ to ‘currentNode’.
  • Concatenate the right part Circular Doubly Linked List ‘rightDLL’ to the current Circular Doubly Linked List and we have already concatenated the left part ‘leftDLL’ with ‘currentNode’. three two of combination possible
    • If ‘leftDLL’ is ‘null/None’
      • Return ‘rightDLL’
    • If ‘rightDLL’ is ‘null/None’
      • Return ‘leftDLL’
    • Else
      • Refer figure ( LEFT DLL + RIGHT DLL).
      • Connect ‘leftDLL’ and ‘rightDLL’ by finding the last nodes of both ‘DLL’.
      • Connect the last node of ‘leftDLL’ to head of ‘rigthDLL’ and last node of ‘rightDLL’ to head of ‘leftDLL’.
      • Return the ‘leftDLL’ as the head of the whole doubly linked list.
         
  • Return the head of the left Circular Doubly Linked List ( ‘leftDLL’ ).
LEFT DLL + CURRENT NODE
LEFT DLL + RIGHT DLL

 

 

Time Complexity

O(N), Where ‘N’ is the number of nodes in the binary tree.

 

We are traversing every node once.

Space Complexity

O(N), Where ‘N’ is the number of nodes in the binary tree.

 

We are using a linear space recursion call stack.

Code Solution
(100% EXP penalty)
Convert A Binary Tree To A Circular Doubly Linked List
Full screen
Console