Minimum swap required to convert binary tree to binary search tree in C++

In this tutorial, we will learn how to find out the minimum number of swaps required to convert a binary tree into a binary search tree (BST). We will try to understand the process in-depth to make us familiar with this type of question.

The inorder traversal of a binary search tree gives the non-decreasing order of its value, in other words, sorts the value in the BST. The minimum number of swaps required to convert the binary tree into a binary search tree is equal to the number of swaps requires to sort the inorder traversal of the binary tree to make it a BST.

We have used the fact that swaps required to convert a binary tree (A) into BST are equal to swaps required to convert the BST into the binary tree (A).

We are given a binary tree in the form of an array arr whose :

index 2*i + 1: is the left child

index 2*i + 2: is the right child

 Procedure followed:

  1. Inorder traversal of Binary tree and store it in Vector (Inorder_form_of_binary_tree).
  2. Make a pair type vector (temp) whose first element if elements of Vector (Inorder_form_of_binary_tree) and second element is the index of the corresponding element.
  3. Then sort this temp vector and then traverse the temp to find out the minimum number of swaps required to track the previous position of the element at index (i) in the Vector (Inorder_form_of_binary_tree ). Keep adding this minimum swaps required to total the number of swaps required (ans) for each element at index i.

Code: Inorder_traversal

void Inorder_traversal(int arr[] , 
                       vector<int> &Inorder_form_of_binary_tree ,
                       int current_index ,int n) {
    //base condition 
    //as we have only n elements in the array 
    if(current_index >= n){
        return ;
    }
    //To traverse the left child of the node
    //with the index equal to current_index 
    Inorder_traversal( arr ,Inorder_form_of_binary_tree ,
                       2*current_index +1  , n ) ;
    Inorder_form_of_binary_tree.push_back(arr[current_index]);
    //To traverse the right child of the node 
    //with the index equal to current_index 
    Inorder_traversal( arr , Inorder_form_of_binary_tree , 
                       2*current_index +2,n ) ;
}

Output :

Input to function arr[]={1 ,2 ,3 ,4 ,6 , 7, 9}
Inorder_traversal of arr :4 2 6 1 7 3 9

Code:Minimum_number_of_swaps_required function

This portion of the code assigns and sorts temp vector.

int Minimum_number_of_swaps_required(vector<int> 
                                      &Inorder_form_of_binary_tree){
   int n=Inorder_form_of_binary_tree.size();
   //This temp vector will contain the sorted 
   vector< pair<int ,int > > temp(n) ;
   
   //First element of pair type vector "temp" is 
   //element of Inorder_form_of_binary_tree 
   //second is element's index in the Inorder_form_of_binary_tree
   for( int  i=0 ; i< n ; i++ ){
    temp[i].first=Inorder_form_of_binary_tree[i];
    temp[i].second=i;
   }

   //Result: temp will look like this :
   //first : 4 2 6 1 7 3 9 
   //second: 0 1 2 3 4 5 6
   //{4, 0} {2 ,1} and so on are paired 

   //This function sorts the temp vector according 
   //to the first element
   sort( temp.begin() , temp.end() );
   //Temp vector after sorting is :
   //first: 1 2 3 4 6 7 9 
   //second:3 1 5 0 2 4 6

 

Output:

 Temp vector Before sorting:
 //first :4 2 6 1 7 3 9 
 //second:0 1 2 3 4 5 6
 Temp vector After sorting:
 //first :1 2 3 4 6 7 9 
 //second:3 1 5 0 2 4 6

The below code does the most important operation. It finds out the minimum swaps need to each element to track to its previous position. Swap_for_ I calculated for each element and then added to ans. And in while loop body we keep on swapping till we do not find out the element whose second is equal to j.

int swaps_for_i = 0 ,ans = 0 ;
   //number_of_swaps_required_to_backtrack
   //the_postion_of_element_before_sorting
   for(int i=0 ; i < temp.size(); i++ ){
      // To check whether element position has changed 
      // after sorting:
       if( i == temp[i].second ){
          continue; 
       }
       else {
          int j = i;
          swaps_for_i = 0 ;
          while( j!= temp[j].second){
           //swapping the first element    
           swap(temp[j].first,  temp[temp[j].second].first); 
           //swapping the second element
           swap(temp[j].second, temp[temp[j].second].second);
           //increment it for a swap made for i
           swaps_for_i++;
          }
       }  
       ans+=swaps_for_i;
   }
  return ans ;
}

 

Output:

Temp vector:Before performing the above operation:
//first :1 2 3 4 6 7 9 
//second:3 1 5 0 2 4 6
  After :
//first :4 2 6 1 7 3 9 
//second:0 1 2 3 4 5 6

 

Code: Driver Code

Below is the driver code called from the main function. It utilizes the above function to calculate the minimum swaps.

void solve (int arr[]  ,int n ) {
    //This vector will store the inorder traversal form  
    //of binary tree , formed by elements in array arr.
      vector< int > Inorder_form_of_binary_tree ;
    //This function will do inorder traversal over arr
     Inorder_traversal( arr , Inorder_form_of_binary_tree , 0 , n);
    //Result obtained is : 4 2 6 1 7 3 9 
    //Their  index    is : 0 1 2 3 4 5 6
    
    cout<<"Inoder form of Binary tree \n";
    for( int i=0 ; i < n ; i++ ){
        cout<<Inorder_form_of_binary_tree[i]<<" ";
    }
    cout<<"\n";
    cout<<"Minimum spaws required ";
    cout<< Minimum_number_of_swaps_required( 
           Inorder_form_of_binary_tree )<<"\n";
}

Code: Main Function

This is the main body which contains the array (binary tree) to be converted to BST.

int main(){

    //Declaring the array and assigning the values.
    int arr[] = {1 ,2 ,3 ,4 ,6 , 7, 9 } ;
    int n = 7 ;
    //This is our driver function
    solve ( arr , n );
    return 0;
}

Output:

Minimum swaps required:3

Leave a Reply

Your email address will not be published. Required fields are marked *