Binary Tree to BST Using an STL Set

Introduction 

Sets are usually known as containers in C++ STL. It is used for storing elements in a particular order. The elements present in the set must be unique.

This article will discuss the conversion of binary tree to BST using an STL set.

Problem Statement 

You are a student of Konoha’s Ninja academy. Iruka sensei gave you a binary tree. You are supposed to convert that Binary Tree to BST using the STL set. The condition given by sensei is that the conversion must be performed in such a way that the original structure of the Binary Tree is preserved. And instead of an array-based solution, you have to use Sets from the C++ STL.

Now let’s see some examples to get a better understanding of the task entrusted by the sensei.

Samples Examples 

Example 1: 

Input: 

Output: 

Example 2:

Input: 

Output:

Explanation: We are given a normal binary tree. Now the binary tree is re-arranged in a binary search tree. The left node of BST will have a smaller value than the node. And the right node will have a larger value than its node.

The leftmost leaf will have the smallest value. And the rightmost leaf will have the largest value in the tree. The value of the rest of the nodes will be according to the principle of BST.

Using STL set 

The main idea of conversion of binary tree to BST using STL set is the insertion, searching, and deletion. We will copy the binary tree items into the set. Then we will copy the item back to the tree using in-order traversal. Since the inorder traversal of the binary tree gives the sorted order of nodes in ascending order. 

Let’s see the algorithm of this approach. 

Algorithm 

1. We will start by defining the structure of the tree node.
2. Then we will make a function to insert a tree element into the set.
3. Now for conversion into BST. Replace the element of the initial tree in BST in an in-order fashion using STL.
4. While doing inorder traversal, copy the binary tree items into a set. 
5. Sets in C++ are implemented using self-balancing binary search trees, so each operation, such as insertion, searching, deletion, and so on, takes O(log n) time.
6. Copy the items of set one by one from the beginning to the tree while traversing the tree in order. When copying each item of a set from the start. We first copy it to the tree while doing in-order traversal. Then remove it from the set.
7. Now print out the BST.

Implementation 

#include <bits/stdc++.h>
using namespace std;
// now defines the structure of a tree node
struct node{
   int data;
   node* left;
   node* right;
};
// now inserts the given tree elements into the set
void insertSet(node* root, set<int> &treeSet){
   if(root){
       insertSet(root->left, treeSet);
       treeSet.insert(root->data);
       insertSet(root->right, treeSet);
   }
}
// now replace the elements of the initial tree with elements in tree Set in in-order fashion
void BinaryTreeIntoBST(node* root, set<int> &treeSet)
{
   if(root){
       BinaryTreeIntoBST(root->left, treeSet);
       root->data = *(treeSet.begin());
       treeSet.erase(treeSet.begin());
       BinaryTreeIntoBST(root->right, treeSet);
   }
}
// Converts Binary tree to BST
void binaryTreeToBST(node* root)
{
   set<int> treeSet;
   // first fill the set
   insertSet(root, treeSet);
   // then replace the elements in initial tree
   BinaryTreeIntoBST(root, treeSet);
}
// to create and return a new node with supplied node value
node* create(int data){
   node *tmp = new node();
   tmp->data = data;
   tmp->left = tmp->right = NULL;
   return tmp;
}
// simple in-order traversal
void inorderimp(node *root){
   if(root){
       inorderimp(root->left);
       cout<<root->data;
       inorderimp(root->right);
   }
}
int main()
{
   // constructing a binary tree
   // same as shown above
   node *root = create(1);
   root->right = create(3);
   root->right->left = create(7);
   root->right->left->left = create(9);
   root->right->left->right = create(5);
   cout<<"Inorder Traversal of given binary tree"<<endl;
   inorderimp(root);cout<<endl;
   binaryTreeToBST(root);
   cout<<"Inorder Traversal of modified tree\n";
   inorderimp(root);
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity 

The time complexity of the above approach for the problem of conversion of Binary tree to BST using STL set is O(nlogn). Here n is the number of elements of the tree. We have the logarithmic factor because of the set we are using. As we know, set data structure requires “nlogn” time to insert, search and delete an element. That is why the time complexity of the approach is O(nlogn).

Space Complexity 

The space complexity of the above approach for the problem of conversion of Binary tree to BST using STL set is O(n). Here we used extra space to store nodes. The algorithm used for conversion has a linear space complexity. Hence, the space complexity of the approach is O(n).
Check out this problem - Largest BST In Binary Tree