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.

           8                     5
         /   \                 /   \
        /     \               /     \
       3       5     —->     3       8
      / \     / \           / \     / \
     /   \   /   \         /   \   /   \
    10    2 4     6       2     4 6    10



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(n) 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 🙂


  • AllergicToBitches