Practice

EASY-MEDIUM

# PREREQUISITES

COMPLETE BINARY TREE

# EXPLANATION:

Since it is CBT the rightmost part will be filled only the left part is filled so it moves in level wise pattern from left to right now every node can be the child of another node or vice versa so we transform the tree into the array . Form the parent of node at position i will be (i-1)/2 . similarly, the left child of node i will be 2i+1 and the right child will be 2i+2 now we can easily perform a check on the array.

# SOLUTION:

``````import java.math.BigInteger;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Scanner;
import java.util.StringTokenizer;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;

{
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
}

{
din = new DataInputStream(new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
}

{
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1)
{
if (c == '\n')
break;
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}

public int nextInt() throws IOException
{
int ret = 0;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do
{
ret = ret * 10 + c - '0';
}  while ((c = read()) >= '0' && c <= '9');

if (neg)
return -ret;
return ret;
}

public long nextLong() throws IOException
{
long ret = 0;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)
do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}

public double nextDouble() throws IOException
{
double ret = 0, div = 1;
while (c <= ' ')
boolean neg = (c == '-');
if (neg)

do {
ret = ret * 10 + c - '0';
}
while ((c = read()) >= '0' && c <= '9');

if (c == '.')
{
while ((c = read()) >= '0' && c <= '9')
{
ret += (c - '0') / (div *= 10);
}
}

if (neg)
return -ret;
return ret;
}

private void fillBuffer() throws IOException
{
buffer[0] = -1;
}

{
fillBuffer();
return buffer[bufferPointer++];
}

public void close() throws IOException
{
if (din == null)
return;
din.close();
}
}
/*----------------------------------------------------------------------------------------------
public static long mod=1000000007;
public static long power(long a, long b)	{
if(b == 0)
return 1;
if(b%2!=0)
}
public static long min(long a, long b)	{
return a<b?a:b;
}
public static long divide(long a,long b)	{
return (a%mod*(power(b, mod-2)%mod))%mod;
}

public static long nCr(long n,long r)	{
long k = min(r, n-r);
for(long i=0;i<k;i++)	{
}
}

public static boolean plaindrome(String str){
StringBuilder sb=new StringBuilder();
sb.append(str);
return (str.equals((sb.reverse()).toString()));
}
public static class Triplet{
long gcd;
long x;
long y;
Triplet(long gcd,long x,long y) {
this.gcd=gcd;
this.x=x;
this.y=y;
}
}

public static Triplet ExtendedEuclideanAlgo(long a,long b) {
if(a==0) {
return new Triplet(b,0,1);
}
Triplet ans=ExtendedEuclideanAlgo(b%a, a);
long x=ans.y-(b/a)*ans.x;
long y=ans.x;
return new Triplet(ans.gcd,x,y);
}

public static long ModInverse(long a,long m) {
Triplet ans=ExtendedEuclideanAlgo(a, m);
if(ans.gcd!=1) {
return -1;
}else {
//m is added to handle negative x
long result= (ans.x%m+m)%m;
return result;
}
}
----------------------------------------------------------------------------------------------*/
public static int find(int node,int arr[]){
int n=arr.length;
int ans=0;
for(int i=0;i<n;i++){
if(arr[i]==node){
ans=i;
break;
}
}
return ans;}
public static void main (String[] args) throws java.lang.Exception
{
StringBuilder sb=new StringBuilder();
int tc=s.nextInt();
while(tc-->0){
int n=s.nextInt();
int q=s.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)arr[i]=s.nextInt();
while(q-->0){
int node=s.nextInt();
int k =find(node,arr);
int ans=(k-1)/2;
int left=1+(2*ans);
int right=2+(2*ans);
//     System.out.print(k+" "+left+" "+right+"  ");
if(k==0){
System.out.println("NO");
continue;
}
if(left<n&&left>=0&&right>=0&&right<n){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}

}
}
``````