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

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 –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <bits/stdc++.h> using namespace std; // Data structure to store a Binary Search Tree node struct Node { int data; Node *left, *right; }; // Function to create a new binary tree node having given key Node* newNode(int key) { Node* node = new Node; node->data = key; node->left = node->right = nullptr; return node; } // Function to perform in-order traversal of the tree void inorder(Node* root) { if (root == nullptr) return; inorder(root->left); cout << root->data << " "; inorder(root->right); } // Function to traverse the binary tree and store its keys in a set void extractKeys(Node *root, auto &set) { // base case if (root == nullptr) return; extractKeys(root->left, set); set.insert(root->data); extractKeys(root->right, set); } // Function to put back keys in set in their correct order in BST // by doing in-order traversal void convertToBST(Node *root, auto &it) { if (root == nullptr) return; convertToBST(root->left, it); root->data = *it; it++; convertToBST(root->right, it); } // main function int main() { /* Construct below tree 8 / \ / \ 3 5 / \ / \ / \ / \ 10 2 4 6 */ Node* root = newNode(8); root->left = newNode(3); root->right = newNode(5); root->left->left = newNode(10); root->left->right = newNode(2); root->right->left = newNode(4); root->right->right = newNode(6); // traverse the binary tree and store its keys in a set set<int> set; extractKeys(root, set); // put back keys present in set in their correct order in BST auto it = set.begin(); convertToBST(root, it); // print the BST inorder(root); return 0; } |

**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

+1

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.