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).
(2 votes, average: 5.00 out of 5)
Loading...
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
+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 🙂