(1) Given a complete binary tree with N nodes and each node have a distinct inte
ID: 3600594 • Letter: #
Question
(1) Given a complete binary tree with N nodes and each node have a distinct integer a, attached with it, find the minimum number of swaps you can make to convert the binary tree into binary search tree. In one swap, you can select any two nodes and swap their values. You will be given the array representation of the binary tree. Root of the tree will be at ao. Left child of root will be at a1 and right child of root will be at a2. Left child of node at array position k will be at a2 k+1 and right child of node at array position k will be at a2.k+2 Input format First line contains an integer, N (1KNs105), denoting the number of nodes. Second line contains N space separated integers, ai (1sais105), denoting the value attached to ith node Output format Print a single integer, denoting the minimum number of swaps needed to convert binary tree into a binary search tree Sample Input: 12 3 Sample Output: Explanation We need only one swap (1,2) to convert the given binary tree into binary search tree 3 After swapping (1, 2) 3Explanation / Answer
import java.util.*;
public class BinaryToBST{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] ar=new int[n];
for(int i=0;i<n;i++){
ar[i]=in.nextInt();
}
int count=0,temp;
for(int i=0;i<n-2;i++){
if(ar[i]>ar[i+1]&&ar[i]<ar[i+2]){
i=i+1;
}else{
if(ar[i]<ar[i+1]){
temp=ar[i];
ar[i]=ar[i+1];
ar[i+1]=temp;
count++;
}
if(ar[i]>ar[i+2]){
temp=ar[i];
ar[i]=ar[i+2];
ar[i+2]=temp;
count++;
}
}
}
System.out.println(count);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.