Minimum swap required to convert binary tree to binary search tree

Introduction 

This article will discuss the problem of finding the minimum number of swaps required to convert the given binary tree into the binary search tree. To solve this problem, there is a prerequisite, and you must know how to calculate the minimum number of swaps to sort the array. To study this, you can refer to this blog of coding ninjas.  

Problem Statement

The problem states that we are given a binary tree and can swap any two nodes in the binary tree. We need to calculate the minimum number of swaps required to convert this given binary tree into the binary search tree. 

Sample Examples 

Input: 

Output: 

The minimum number of swaps required is: 3

Explanation:

Swap 1: Swap Node 80 with node 50. 
Swap 2: Swap node 90 with node 100. 
Swap 3: Swap node 100 with node 70. 

Input: 

Output: 

The minimum number of swaps required is: 2

Explanation:

Swap 1: Swap nodes 1 and 4 
Swap 2: Swap nodes 4 and 3

Solution Approach 

Prerequisite: Minimum number of swaps to sort the array 

The solution is based on the idea that inorder traversal of the binary search tree is always sorted, so we will calculate the inorder traversal of the binary tree and store it in the array. Then we will calculate the minimum number of swaps to sort the array. It will give us the minimum number of swaps to convert the given binary tree into the binary search tree. 

Steps of Algorithm 

• Take the input of the binary tree in level order traversal form. 
• Do the inorder traversal of the binary tree, and store inorder traversal into the array.
• Now calculate the minimum number of swaps required to sort the array. 
• The result of the minimum number of swaps to sort the array will be our required answer. 
• Print the answer.  

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
void inorderTraversal(vector<int> arr, vector<int> &inorder, int root)
{
    if (root >= arr.size())
        return;
    // recur for the left subtree
    inorderTraversal(arr, inorder, 2 * root + 1);
    // pushing the root data into the vector
    inorder.push_back(arr[root]);
    // recur for the right subtree
    inorderTraversal(arr, inorder, 2 * root + 2);
}
static bool cmp(vector<int> &x, vector<int> &y)
{
    return x[0] < y[0];
}
int minimumSwap(vector<int> &inorder)
{
    // conatiner to store the element along with the index
    vector<vector<int>> v;
    int n = inorder.size();
    int swaps = 0;
    for (int i = 0; i < n; i++)
    {
        vector<int> temp;
        temp.push_back(inorder[i]);
        temp.push_back(i);
        v.push_back(temp);
    }
    // sorting the array
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < n; i++)
    {
        // if indexing matches with the element
        if (i == v[i][1])
            continue;
        else
        {
            // swapping of the elements
            swap(v[i][0], v[v[i][1]][0]);
            swap(v[i][1], v[v[i][1]][1]);
        }
        // is the second element is not equal to i
        if (i != v[i][1])
            --i;
        swaps++;
    }
    return swaps;
}
int main()
{
    vector<int> arr = {50, 60, 70, 80, 90, 100, 110};
    // array to store the inorder traversal of the above tree
    int n = arr.size();
    vector<int> inorder;
    inorderTraversal(arr, inorder, 0);
    // printing the inorder array
    // for (int i = 0; i < n; i++)
    //  cout << inorder[i] << " ";
    // cout << endl;
    cout << "The minimum number of swaps required are : " << minimumSwap(inorder) << endl;
}

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

Run Code

Output:

The minimum number of swaps required is: 3 

Complexity Analysis

Time Complexity: O(N)

We are only doing linear traversal of the arrays, so time complexity is linear to find the minimum number of swaps to convert binary tree to binary search tree. 

Space Complexity: O(N)

We are creating a temporary array to store the inorder traversal of the given tree, so space complexity is O(N).