PROBLEM NAME:
FIND LEVEL
PROBLEM LINK:
DIFFICULTY
EASY MEDIUM
PREREQUISITES:
COMPLETE BINARY TREE
PROBLEM DESCRIPTION
You are given a CBT (COMPLETE BINARY TREE) with N nodes and Q quires are asked. Find level at which node asked in quires is present.
NOTE:− Root of tree is at level 1.
APPORACH:
Since it is CBT a node can have maximum 2 childrens
we know in cbt all levels are filled except the last one and the way of filling level is from left to right i.e. if left nodes are not filled then we cannot fill right nodes .
so on first level there is at max 1 node ,in 2nd level maximum nodes are 2 ,in 3rd there are 4 and so on so if we observe it this follows pattern of 2^n now for each query if we know the index at which the node is present and find which is nearest number less thhan index divisible by 2^k.
so k+1 is the level at which node is present.
#include <iostream>
using namespace std;
int find_index(int []arr,int k,int n){
for(int i=0;i<n;i++){
if(arr[i]==k)return i+1;
}
return -1;}
int main() {
int tc;
cin>>tc;
while(tc-->0){
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)cin>>arr[i];
int q;
cin>>q;
while(q-->0){
int k;
cin>>k;
int idx=find_index(arr,k,n);
int ans=1;
while(idx!=1&&idx!=-1){
idx=idx/2;
ans++;
}
if(idx==-1){
cout<<-1<<"\n";
}else{
cout<<ans<<"\n";
}
}
}
return 0;
}