Add a method called int subtreeSize(AVLNode N) to AVLTree.java class that takes a node N and return the number of nodes in the subtree rooted at N included N itself. The running time of your method should be O(1) in the worst-case. [Hint: Add another field called int size to AVLNode.java class and update size parameter during insertion].

public class AVLNode{

int key;

int height;

AVLNode left;

AVLNode right;

//Constructor

public AVLNode(int k){

key=k;

height=0;

left=null;

right=null;

}

}

import java.util.*;

import java.lang.Math;

import java.io.*;

import java.lang.Integer;

public class AVLTree{

AVLNode root;

//constructor

public AVLTree(){

root=null;

}

//helper function

public void insert(int k){

AVLNode newnode = new AVLNode(k); // make new node

if (root==null){

root=newnode;

}

else {

root=AVLinsert(newnode,root);

}

}

//AVLinsert is a recursive function

public AVLNode AVLinsert(AVLNode newnode, AVLNode parent){

AVLNode temp=parent;

if (newnode.key

if(parent.left==null){

parent.left=newnode;}

else{

parent.left=AVLinsert(newnode, parent.left);

if (Height(parent.left)-Height(parent.right)==2){

if (newnode.key

temp=rightrotation(parent); // apply rightrotation

}

else {

temp=leftrightrotation(parent); //apply leftright rotation

}

}

}

}

else if (newnode.key>parent.key){

if(parent.right==null){

parent.right=newnode;

}

else{

parent.right=AVLinsert(newnode, parent.right);

if (Height(parent.left)-Height(parent.right)==-2){

if (newnode.key>parent.right.key){

temp=leftrotation(parent); //apply left rotation

}

else {

temp=rightleftrotation(parent); //apply rightleft rotation

}

}

}

}

else System.out.println("Duplicate Keys");

if (parent.left==null && parent.right!=null){

parent.height=parent.right.height+1;

}

else if (parent.right==null && parent.left!=null){

parent.height=parent.left.height+1;

}

else if ((parent.right!=null) && (parent.left!=null)){

parent.height=Math.max(parent.left.height,parent.right.height)+1;

}

return temp;

}

public AVLNode rightrotation(AVLNode parent){ //right rotation for LL Case

AVLNode temp=parent.left;

parent.left=temp.right;

temp.right=parent;

parent.height=Math.max(Height(parent.left),Height(parent.right))+1; // update the height after rotation

temp.height=Math.max(Height(temp.left),Height(temp.right))+1; //update the height after rotation

return temp;

}

public AVLNode leftrotation(AVLNode parent){ //left rotation for RR Case

AVLNode temp=parent.right;

parent.right=temp.left;

temp.left=parent;

parent.height=Math.max(Height(parent.left),Height(parent.right))+1; // update the height after rotation

temp.height=Math.max(Height(temp.left),Height(temp.right))+1; //update the height after rotation

return temp;

}

public AVLNode leftrightrotation(AVLNode parent){ //leftright rotation for RL Case

parent.left=leftrotation(parent.left);

AVLNode temp=rightrotation(parent);

return temp;

}

public AVLNode rightleftrotation(AVLNode parent){ //rightleft rotation for LR Case

parent.right=rightrotation(parent.right);

AVLNode temp=leftrotation(parent);

return temp;

}

public int Height(AVLNode x){ // return height of tree rooted at x

if (x == null){ // If node is null take height= -1

return -1;}

else {

return x.height;}

}

public boolean empty(){ //test if the tree is empty

if (root==null){

return true;}

return false;

}

public void printLevelOrder(){ //print the in level order

int h=root.height;

for (int i=0; i<=h;i++){

printLevel(root,i);

System.out.println();

}

}

public void printLevel(AVLNode root, int level){

if(root==null){

return; }

if(level==0){

System.out.print(root.key+" "); }

else if(level>0){

printLevel(root.left, level-1);

printLevel(root.right, level-1);

}

}

public void preorder(AVLNode root){

if (root==null){

return;}

else{

System.out.print(root.key+" ");

preorder(root.left);

preorder(root.right);

}

}

public void inorder(AVLNode root){

if (root==null){

return;}

else{

inorder(root.left);

System.out.print(root.key+" ");

inorder(root.right);

}

}

public void postorder(AVLNode root){

if (root==null){

return;}

else{

postorder(root.left);

postorder(root.right);

System.out.print(root.key+" ");

}

}

public static void main(String[] args){

AVLTree T=new AVLTree();

T.insert(5);

T.insert(4);

T.insert(3);

T.insert(6);

T.insert(7);

T.insert(2);

T.insert(1);

T.printLevelOrder();

System.out.println(" ");

System.out.print("Preorder Traversal :");

T.preorder(T.root);

System.out.println(" ");

System.out.print("Inorder Traversal :");

T.inorder(T.root);

System.out.println(" ");

System.out.print("Postorder Traversal:");

T.postorder(T.root);

System.out.println(" ");

}

}