Binary Tree To Circular Doubly Linked List

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
1 upvote
Asked in company
SAP Labs

Problem statement

You have been given a binary tree of integers. You are supposed to convert the given binary tree into a circular doubly linked list (In place, i.e. without using any extra space). The nodes of the circular doubly linked list must follow the same order as the inorder traversal of the given binary tree. The head of the circular doubly linked list must point to the first node in the inorder traversal of the binary tree. You are supposed to use the left and the right pointers of the binary tree as the 'prev' and 'next' pointers respectively of the circular doubly linked list.

Example : 
Consider the binary tree below and the following circular doubly linked list.

Example

The head node of the above doubly linked list should be the node with value 12.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place. So -1 would not be a part of the tree nodes.

For example, the input for the tree depicted in the below image will 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 each test case, print the nodes of the circular doubly linked list separated by a single space.

Print the output of each test case in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= 'T' <= 100
1 <= 'N' <= 3000
0 <= 'data' <= 10^5 and 'data' != -1

Where 'data' is the value of the binary tree node.

Time Limit: 1 sec
Sample Input 1 :
2
3 2 5 -1 -1 -1 -1
5 9 -1 1 -1 -1 1 9 -1 -1 -1
Sample Output 1 :
2 3 5
1 9 1 9 5
Explanation of Sample Input 1 :
For the first test case, the inorder traversal of the binary tree is {2, 3, 5 }.

For the second test case, the inorder traversal of the binary tree is {1, 9, 1, 9, 5  }.
Sample Input 2 :
2
1 -1 2 -1 -1
5 3 -1 2 -1 8 4 -1 -1 -1 -1
Sample Output 2 :
1 2
8 2 4 3 5
Explanation of Sample Input 2 :
For the first test case, the inorder traversal of the given binary tree is {1, 2 }.

For the second test case,  the inorder traversal of the binary tree is {8, 2, 4, 3, 5  }.
Hint

Can you think about manipulating with the left node and the right node of the binary tree separately?

Approaches (1)
Recursion Based Approach

The idea is to use inorder/postorder traversal to recursively convert the left and right subtrees to doubly circular linked lists and then merge the results of the left and the right subtrees with the root to get the final circular linked list.

 

The steps are as follows:

 

  1. Define a function postorderTraversal(root) where root denotes the current node of the binary tree. Also, this function will return TreeNode pointer pointing to the head to the circular doubly linked list formed by all nodes in the subtree of root including root itself., Where left and the right pointers of the binary tree as the prev and next pointers respectively of the circular doubly linked list.
  2. For every node recur for the left subtree and right subtree.
    1. TreeNode* leftSubtree = postOrderTraversal(root->left)
    2. TreeNode* rightSubtree = postOrderTraversal(root->right)
    3. Change the left and right pointer of the current node to point to itself.
    4. Merge leftSubtree and the root node.
    5. Now merge the rightSubtree as well.
    6. Return the head of the merged circular doubly linked list.

For merging any two circular doubly linked lists, let’s say listOne and listTwo follow the below steps:

 

  1. Store the head of the listOne into the headListOne and the head of the listTwo into the headListTwo.
  2. Now the left node of headListOne will point to the last node of the listOne linked list since the linked list is circular. Similarly, the left node of headListTwo will point to the last node of the listTwo linked list. Let’s say the last node of the listOne linked list is lastListOne”, and the last node of the listTwo linked list is lastListTwo.
  3. Now change the right pointer of lastListOne and connect it to headListTwo.  Also, change the left pointer of headListTwo and connect it to lastListOne.
  4. Change the left pointer of headListOne and connect it to lastListTwo. Similarly, point the right pointer of lastListTwo to headListOne.
  5. Return the head of the circular doubly linked list.
Time Complexity

O(N), where N is the total number of nodes in the binary tree.

 

We are doing postorder traversal in which we will visit each node once. There are N nodes to visit, so this will take O(N) time. Also, we are merging two circular doubly linked lists, and this is done in O(1) time by changing the pointers of the first and the last nodes. Thus, the overall time complexity will be O(N).

Space Complexity

O(N), where N is the total number of nodes in the binary tree.

 

We are doing postorder traversal in which the recursion stack can grow up to size N in case of a skewed binary tree, so the total recursion stack space is O(N). Also, we are doing all the changes In-place, i.e. we are not using any extra space for creating the circular doubly linked list.  Thus, the overall space complexity will be O(N).

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