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.
Below is C++/Java implementation of the idea:
C++
|
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 91 |
#include <iostream> #include <set> 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
Java
|
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 |
import java.util.TreeSet; import java.util.Iterator; import java.util.Set; // Data structure to store a Binary Search Tree node class Node { int data; Node left = null, right = null; Node(int data) { this.data = data; } } class BST { // Function to perform in-order traversal of the tree public static void inorder(Node root) { if (root == null) { return; } inorder(root.left); System.out.print(root.data + " "); inorder(root.right); } // Function to traverse the binary tree and store its keys in a set public static void extractKeys(Node root, Set set) { // base case if (root == null) { return; } extractKeys(root.left, set); set.add(root.data); extractKeys(root.right, set); } // Function to put back keys in set in their correct order in BST // by doing in-order traversal public static void convertToBST(Node root, Iterator<Integer> it) { if (root == null) { return; } convertToBST(root.left, it); root.data = it.next(); convertToBST(root.right, it); } // main function public static void main(String[] args) { /* Construct below tree 8 / \ / \ 3 5 / \ / \ / \ / \ 10 2 4 6 */ Node root = new Node(8); root.left = new Node(3); root.right = new Node(5); root.left.left = new Node(10); root.left.right = new Node(2); root.right.left = new Node(4); root.right.right = new Node(6); // traverse the binary tree and store its keys in a set Set<Integer> set = new TreeSet<>(); extractKeys(root, set); // put back keys present in set in their correct order in BST Iterator<Integer> it = set.iterator(); convertToBST(root, it); // print the BST inorder(root); } } |
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.
Jesus, good concern!
We have used set only because the keys are always retrieved in sorted order. We can also use vector or a array but then we have to sort the keys as already mentioned in the post.
Coming back to your concern, yes we’re building a Binary Search Tree (where original structure might not be maintained) so that we could build a Binary Search Tree where original structure is maintained.
Need to change from HashSet to TreeSet to get the elements in sorted order
Thanks a lot for bringing this issue to our notice. We have updated the code. Happy coding 🙂