Problem link is:https://www.geeksforgeeks.org/count-smaller-elements-on-right-side/
my code is using AVL Tree taught by Garima ma’am,please help me find out why my code is not getting accepted.I am facing NullPinterException
code is:
package BinaryTree;
import java.util.Scanner;
import BinaryTree.AvlTrees.node;
public class GReaterOnRHS {
class node{
node left;
node right;
int size=1;
int height=1;
int data;
}
private node root;
public void insert(int item,int pos,int[] ans) {
this.root=insert(this.root,item,pos,ans);
}
private node insert(node nn,int item,int pos,int[] ans) {
if(nn==null) {
node addnode=new node();
addnode.data=item;
addnode.height=1;
addnode.size=1;
return addnode;
}
if(item<=nn.data) {
nn.left=insert(nn.left,item,pos,ans);
}
else {
ans[pos]=ans[pos]+size(nn.left)+1;
nn.right=insert(nn.right,item,pos,ans);
}
nn.size=size(nn.left)+size(nn.right)+1;
nn.height=Math.max(height(nn.left),height(nn.right))+1;
int nnbf=bf(nn);
//LL rotation
if(nnbf>1 && item<nn.left.data) {
// System.out.println("LL ROTATION " + item + " " + nn.data);
// display();
return rightrotate(nn);
}
// RR rotation
if(nnbf<-1 && item>nn.right.data) {
return leftrotate(nn);
}
//LR rotation
if(nnbf>1 && item>nn.left.data) {
nn.left=leftrotate(nn.left);
return rightrotate(nn);
}
//RL Rotation
if(nnbf<-1 && item<nn.right.data) {
nn.right=rightrotate(nn.right);
return leftrotate(nn);
}
return nn;
}
private node leftrotate(node nn) {
node b=nn.right;
node y=b.left;
b.left=nn;
nn.right=y;
nn.height=Math.max(height(nn.right),height(nn.left))+1;
b.height=Math.max(height(b.left),height(b.right))+1;
nn.size=size(nn.left)+size(nn.right)+1;
b.size=size(b.left)+size(b.right)+1;
return b;
}
private node rightrotate(node nn) {
node b=nn.left;
node y=b.right;
b.right=nn;
nn.left=y;
nn.height=Math.max(height(nn.right),height(nn.left))+1;
b.height=Math.max(height(b.left),height(b.right))+1;
nn.size=size(nn.left)+size(nn.right)+1;
b.size=size(b.left)+size(b.right)+1;
return b;
}
private int bf(node nn) {
if(nn==null) {
return 0;
}
return height(nn.left)-height(nn.right);
}
private int size(node nn) {
if(nn==null) {
return 0;
}
return nn.size;
}
private int height(node nn) {
if(nn==null) {
return 0;
}
return nn.height;
}
public void display() {
display(this.root);
}
private void display(node nn) {
String ans = "";
int left = 0;
int right = 0;
if (nn.left != null) {
left = 1;
ans = ans + nn.left.data + " => ";
} else {
ans = ans + "null => ";
}
ans = ans + nn.data + " <= ";
if (nn.right != null) {
right = 1;
ans = ans + nn.right.data;
} else {
ans = ans+"null";
}
System.out.println(ans);
if (left == 1) {
display(nn.left);
}
if (right == 1) {
display(nn.right);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner=new Scanner(System.in);
int t=scanner.nextInt();
for(int test=0;test<t;test++) {
GReaterOnRHS tree=new GReaterOnRHS();
int n=scanner.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++) {
arr[i]=scanner.nextInt();
}
int[] ans=new int[n];
for(int i=n-1;i>=0;i--) {
tree.insert(arr[i],i,ans);
}
for(int i=0;i<n;i++) {
System.out.print(ans[i] + " ");
}
System.out.println();
}
}
}