Minimum swap required to convert binary tree to binary search tree
Last Updated :
22 Sep, 2023
Given the array representation of Complete Binary Tree i.e, if index i is the parent, index 2*i + 1 is the left child and index 2*i + 2 is the right child. The task is to find the minimum number of swap required to convert it into Binary Search Tree.
Examples:
Input : arr[] = { 5, 6, 7, 8, 9, 10, 11 }
Output : 3
Binary tree of the given array:
Swap 1: Swap node 8 with node 5.
Swap 2: Swap node 9 with node 10.
Swap 3: Swap node 10 with node 7.
So, minimum 3 swaps are required.
Input : arr[] = { 1, 2, 3 }
Output : 1
Binary tree of the given array:
After swapping node 1 with node 2.
So, only 1 swap required.
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
Approach :
The idea is to use the fact that inorder traversal of Binary Search Tree is in increasing order of their value.
So, find the inorder traversal of the Binary Tree and store it in the array and try to sort the array. The minimum number of swap required to get the array sorted will be the answer.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>
using namespace std;
void inorder(int a[], std::vector<int> &v,
int n, int index)
{
if(index >= n)
return;
inorder(a, v, n, 2 * index + 1);
v.push_back(a[index]);
inorder(a, v, n, 2 * index + 2);
}
int minSwaps(std::vector<int> &v)
{
std::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[] = { 5, 6, 7, 8, 9, 10, 11 };
int n = sizeof(a) / sizeof(a[0]);
std::vector<int> v;
inorder(a, v, n, 0);
cout << minSwaps(v) << endl;
}
|
Java
import java.util.*;
public class GFG{
static class Pair{
int first, second;
Pair(int a, int b){
first = a;
second = b;
}
}
static void inorder(int a[], Vector<Integer> v, int n, int index)
{
if(index >= n)
return;
inorder(a, v, n, 2 * index + 1);
v.add(a[index]);
inorder(a, v, n, 2 * index + 2);
}
public static int minSwaps(Vector<Integer> arr)
{
int n = arr.size();
ArrayList < Pair > arrpos = new ArrayList < Pair > ();
for (int i = 0; i < n; i++)
arrpos.add(new Pair(arr.get(i), i));
arrpos.sort(new Comparator<Pair>()
{
@Override
public int compare(Pair o1, Pair o2)
{
return o1.first - o2.first;
}
});
Boolean[] vis = new Boolean[n];
Arrays.fill(vis, false);
int ans = 0;
for (int i = 0; i < n; i++)
{
if (vis[i] || arrpos.get(i).second == i)
continue;
int cycle_size = 0;
int j = i;
while (!vis[j])
{
vis[j] = true;
j = arrpos.get(j).second;
cycle_size++;
}
if(cycle_size > 0)
{
ans += (cycle_size - 1);
}
}
return ans;
}
public static void main(String args[])
{
int a[] = { 5, 6, 7, 8, 9, 10, 11 };
int n = a.length;
Vector<Integer> v = new Vector<Integer>();
inorder(a, v, n, 0);
System.out.println(minSwaps(v));
}
}
|
Python3
def inorder(a, n, index):
global v
if (index >= n):
return
inorder(a, n, 2 * index + 1)
v.append(a[index])
inorder(a, n, 2 * index + 2)
def minSwaps():
global v
t = [[0, 0] for i in range(len(v))]
ans = -2
for i in range(len(v)):
t[i][0], t[i][1] = v[i], i
t, i = sorted(t), 0
while i < len(t):
if (i == t[i][1]):
i += 1
continue
else:
t[i][0], t[t[i][1]][0] = t[t[i][1]][0], t[i][0]
t[i][1], t[t[i][1]][1] = t[t[i][1]][1], t[i][1]
if (i == t[i][1]):
i -= 1
i += 1
ans += 1
return ans
if __name__ == '__main__':
v = []
a = [ 5, 6, 7, 8, 9, 10, 11 ]
n = len(a)
inorder(a, n, 0)
print(minSwaps())
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class GFG {
public class Pair {
public int first, second;
public Pair(int a, int b)
{
first = a;
second = b;
}
}
public static void inorder(int[] a, List<int> v, int n,
int index)
{
if (index >= n)
return;
inorder(a, v, n, 2 * index + 1);
v.Add(a[index]);
inorder(a, v, n, 2 * index + 2);
}
public static int minSwaps(List<int> arr)
{
int n = arr.Count();
List<Pair> arrpos = new List<Pair>();
for (int i = 0; i < n; i++)
arrpos.Add(new Pair(arr[i], i));
arrpos.Sort((x, y) => x.first - y.first);
bool[] vis = new bool[n];
for (int i = 0; i < n; i++)
vis[i] = false;
int ans = 0;
for (int i = 0; i < n; i++) {
if (vis[i] || arrpos[i].first == i)
continue;
int cycle_size = 0;
int j = i;
while (!vis[j]) {
vis[j] = true;
j = arrpos[j].second;
cycle_size++;
}
if (cycle_size > 0)
ans += (cycle_size - 1);
}
return ans;
}
public static void Main(string[] args)
{
int[] a = { 5, 6, 7, 8, 9, 10, 11 };
int n = a.Length;
List<int> v = new List<int>();
inorder(a, v, n, 0);
Console.WriteLine(minSwaps(v));
}
}
|
Javascript
<script>
function inorder(a, n, index)
{
if (index >= n)
return
inorder(a, n, 2 * index + 1)
v.push(a[index])
inorder(a, n, 2 * index + 2)
}
function minSwaps()
{
let t=new Array(v.length);
let ans = -2
for(let i=0;i<v.length;i++)
{
t[i]=new Array(2);
for(let j=0;j<2;j++)
{
t[i][j]=0;
}
}
for(let i=0;i<v.length;i++)
{
t[i][0]=v[i];
t[i][1]=i;
}
t.sort(function(a,b){return a[0] - b[0];});
let i=0;
while(i<t.length)
{
if (i == t[i][1])
{ i += 1;
continue;
}
else{
t[i][0], t[t[i][1]][0] = t[t[i][1]][0], t[i][0];
t[i][1], t[t[i][1]][1] = t[t[i][1]][1], t[i][1];
}
if (i == t[i][1])
i -= 1;
i += 1;
ans += 1;
}
return ans;
}
let v=[];
let a=[ 5, 6, 7, 8, 9, 10, 11];
let n=a.length;
inorder(a, n, 0);
document.write(minSwaps());
</script>
|
Time Complexity: O(n*logn)
Auxiliary Space: O(n) because it is using extra space for array
Exercise: Can we extend this to normal binary tree, i.e., a binary tree represented using left and right pointers, and not necessarily complete?
Please Login to comment...