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


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 🙂

Get great deals at Amazon

Leave a Reply

newest oldest most voted
Notify of



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.