Binary Trees: Minimum swap required to convert binary tree to binary search tree

Problem Statement:

You are given an array representation of a complete binary tree.

You need to find the minimum swaps required to convert into BST.

Example

Consider the array: {1, 2, 3}

Binary tree will be:

        1
       / \
      2   3

After swapping node 1 and 2, the tree will be:

        2
       / \
      1   3

So there is only 1 swap required

Solution

The solution is very simple.

You need to do a inorder traversal and store it in an vector.

Then you need to find out the minimum number of swaps to sort the array.

Why do we need to do perform inorder traversal of the BT?

Because when you do an inorder traversal of a BST, you will get the values in increasing order.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <unordered_map> 

using namespace std;

void inorder_traversal(int a[], vector<int> &v, int n, int index)
{
    if(index >= n)
        return;
    inorder_traversal(a, v, n, 2 * index + 1);
     
    // push elements in vector
    v.push_back(a[index]);

    inorder_traversal(a, v, n, 2 * index + 2);
}
 
int get_min_swaps(std::vector<int> &v)
{
    vector<pair<int,int> > t(v.size());
    int ans = 0;

    for(int i = 0; i < v.size(); i++)
        t[i].first = v[i], t[i].second = i;
     
    sort(t.begin(), t.end());
    for(int i = 0; i < t.size(); i++)
    {
        if(i == t[i].second)
            continue;
        else
        {
            swap(t[i].first, t[t[i].second].first);
            swap(t[i].second, t[t[i].second].second);
        }
         
        if(i != t[i].second)
            --i;
        ans++;
    }
    return ans;
}
 
int main()
{
    int a[] = { 1, 2, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    std::vector<int> v;

    inorder_traversal(a, v, n, 0);

    cout << "The minimum swaps required to make the BT to BST is "<<get_min_swaps(v) << endl;
}

Output:

The minimum swaps required to make the BT to BST is 1