Link nodes present in each level of a binary tree in the form of a linked list

Given a binary tree, write an efficient algorithm to link nodes at the same level in the form of a linked list like structure.

 

For example, convert binary tree to the left to binary tree to right

 
Link Nodes

 
We can solve this problem in linear time by using Hashing. The idea is to traverse the tree in preorder fashion and store nodes present at each level in a map from left to right. Then after every node is proccessed, we iterate through the map and for each level, we set next node for every node present in it.

Here’s a C++ program that demonstrates it:

 

Download   Run Complete Code

Output:

1 -> null
2 -> 3 -> null
4 -> 5 -> 6 -> null
7 -> 8 -> null

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n) for the unordered map.

 

How can we solve this using constant space?

 

The idea is to traverse the tree in preorder fashion and ensure that all nodes at the current level is linked before all nodes at the next level i.e. next pointer of the parent nodes is set before its children.

Then we update the next pointer of parent’s left child to parent’s right child. If right child doesn’t exist, we link parent’s left child to first node in the next level. Similarly, we update the next pointer of parent’s right child to first node in the next level. If we follow this recursively for left and right subtrees, we will end up having connected nodes at each level.

 

Download   Run Code

Output:

1 -> null
2 -> 3 -> null
4 -> 5 -> 6 -> null
7 -> 8 -> null

 
The time complexity of above solution is O(n2) and takes implicit space for the call stack. We can easily convert above program to non-recursive one which takes O(1) space. The iterative version can be seen here.

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Neil
Guest

excellent!!