Convert a Binary Tree to BST by maintaining its original structure

Convert a given binary tree to BST (Binary Search Tree) by keeping original structure of the binary tree intact.

 

For example, consider binary tree shown on the left side below. It should be converted to BST shown on the right.

 
Binary Tree to BST
 


 

The idea is to traverse the Binary Tree and store its keys in a set. We know that an in-order traversal of a binary search tree returns the nodes in sorted order, so we traverse the tree again in in-order fashion and put back the keys present in set (in sorted order) back to their correct position in BST.

The advantage of using set over vector/array is that the keys are always retrieved in sorted order from set. If we use vector/array, we have to sort the keys first before inserting them back.

 
C++ implementation –
 

Download   Run Code

Output:

2 3 4 5 6 8 10

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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
AllergicToBitches
AllergicToBitches

+1

Jesus
Jesus

Set is implemented as a Binary Search Tree.

You’re literally building a Binary Search Tree so that you can build a Binary Search Tree.

wpDiscuz