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++
// C++ program for Minimum swap required// to convert binary tree to binary search tree#include<bits/stdc++.h>using namespace std;// Inorder Traversal of Binary Treevoid inorder(int a[], std::vector<int> &v, int n, int index){ // if index is greater or equal to vector size if(index >= n) return; inorder(a, v, n, 2 * index + 1); // push elements in vector v.push_back(a[index]); inorder(a, v, n, 2 * index + 2);}// Function to find minimum swaps to sort an arrayint 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++) { // second element is equal to i if(i == t[i].second) continue; else { // swapping of elements swap(t[i].first, t[t[i].second].first); swap(t[i].second, t[t[i].second].second); } // Second is not equal to i if(i != t[i].second) --i; ans++; } return ans;}// Driver codeint 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;}// This code is contributed by code_freak |
Java
// Java program for Minimum swap required// to convert binary tree to binary search treeimport java.util.*;public class GFG{ // Pair class static class Pair{ int first, second; Pair(int a, int b){ first = a; second = b; } } // Inorder Traversal of Binary Tree static void inorder(int a[], Vector<Integer> v, int n, int index) { // if index is greater or equal to vector size if(index >= n) return; inorder(a, v, n, 2 * index + 1); // push elements in vector v.add(a[index]); inorder(a, v, n, 2 * index + 2); } // Function returns the // minimum number of swaps // required to sort the array // Refer : 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)); // Sort the array by array element values to // get right position of every element as the // elements of second array. arrpos.sort(new Comparator<Pair>() { @Override public int compare(Pair o1, Pair o2) { return o1.first - o2.first; } }); // To keep track of visited elements. Initialize // all elements as not visited or false. Boolean[] vis = new Boolean[n]; Arrays.fill(vis, false); // Initialize result int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // already swapped and corrected or // already present at correct pos if (vis[i] || arrpos.get(i).second == i) continue; // find out the number of node in // this cycle and add in ans int cycle_size = 0; int j = i; while (!vis[j]) { vis[j] = true; // move to next node j = arrpos.get(j).second; cycle_size++; } // Update answer by adding current cycle. if(cycle_size > 0) { ans += (cycle_size - 1); } } // Return result return ans; } // Driver code 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
# Python3 program for Minimum swap required# to convert binary tree to binary search tree# Inorder Traversal of Binary Treedef inorder(a, n, index): global v # If index is greater or equal to # vector size if (index >= n): return inorder(a, n, 2 * index + 1) # Push elements in vector v.append(a[index]) inorder(a, n, 2 * index + 2)# Function to find minimum swaps# to sort an arraydef 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): # break # second element is equal to i if (i == t[i][1]): i += 1 continue else: # Swapping of elements 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] # Second is not equal to i if (i == t[i][1]): i -= 1 i += 1 ans += 1 return ans# Driver Codeif __name__ == '__main__': v = [] a = [ 5, 6, 7, 8, 9, 10, 11 ] n = len(a) inorder(a, n, 0) print(minSwaps())# This code is contributed by mohit kumar 29 |
C#
// C# program for Minimum swap required// to convert binary tree to binary search treeusing System;using System.Collections.Generic;using System.Linq;class GFG { // Pair class public class Pair { public int first, second; public Pair(int a, int b) { first = a; second = b; } } // Inorder Traversal of Binary Tree public static void inorder(int[] a, List<int> v, int n, int index) { // if index is greater or equal to vector size if (index >= n) return; inorder(a, v, n, 2 * index + 1); // push elements in vector v.Add(a[index]); inorder(a, v, n, 2 * index + 2); } // Function returns the // minimum number of swaps // required to sort the array // Refer : 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)); // Sort the array by array element values to // get right position of every element as the // elements of second array. arrpos.Sort((x, y) => x.first - y.first); // To keep track of visited elements. Initialize // all elements as not visited or false. bool[] vis = new bool[n]; for (int i = 0; i < n; i++) vis[i] = false; // Initialize result int ans = 0; // Traverse array elements for (int i = 0; i < n; i++) { // already swapped and corrected or // already present at correct pos if (vis[i] || arrpos[i].first == i) continue; // find out the number of node in // this cycle and add in ans int cycle_size = 0; int j = i; while (!vis[j]) { vis[j] = true; // move to next node j = arrpos[j].second; cycle_size++; } // Update answer by adding current cycle. if (cycle_size > 0) ans += (cycle_size - 1); } // Return result return ans; } // Driver code 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)); }}// This Code is contributed by Tapesh(tapeshdua420) |
Javascript
<script>// Javascript program for Minimum swap required// to convert binary tree to binary search tree// Inorder Traversal of Binary Treefunction inorder(a, n, index){ // If index is greater or equal to // vector size if (index >= n) return inorder(a, n, 2 * index + 1) // Push elements in vector v.push(a[index]) inorder(a, n, 2 * index + 2)}// Function to find minimum swaps to sort an arrayfunction 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) { // break // second element is equal to i if (i == t[i][1]) { i += 1; continue; } else{ // Swapping of elements 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]; } // Second is not equal to i if (i == t[i][1]) i -= 1; i += 1; ans += 1; } return ans; }// Driver codelet v=[];let a=[ 5, 6, 7, 8, 9, 10, 11];let n=a.length;inorder(a, n, 0);document.write(minSwaps()); // This code is contributed by patel2127</script> |
Output
3
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?
This article is contributed by Anuj Chauhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
