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.

Convert 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.

Below is C++/Java implementation of the idea:


Download   Run Code


2 3 4 5 6 8 10


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).

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

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.


Need to change from HashSet to TreeSet to get the elements in sorted order