My question is regarding Page 163 Problem 419 of Data Struct

My question is regarding Page 163. Problem 4.19 of Data Structures and Algorithm Analysis in Java (3rd Edition)

Draw the tree after each insertion, and label the nodes with their balance factors. If a rotation occurs, write the name of the rotation (i.e., LL, RR, LR, or RL).

Solution

package myProject;

//Insertion in AVL Tree
class Node
{
   int key, height;
   Node left, right;

   //Parameterized constructor
   Node(int d)
   {
       key = d;
       height = 1;
   }//End of constructor
}//End of class

//To constructor an avl tree
public class AVLTree
{

   Node root;

   // To get height of the tree
   int height(Node N)
   {
       if (N == null)
           return 0;

       return N.height;
   }//End of method

   // To get maximum of two integers
   int findMax(int first, int sec)
   {
       return (first > sec) ? first : sec;
   }//End of method

   // To right rotate subtree rooted with y
   Node rightRotate(Node y)
   {
       Node x = y.left;
       Node T2 = x.right;

       // Rotation Operation
       x.right = y;
       y.left = T2;

       // Update heights
       y.height = findMax(height(y.left), height(y.right)) + 1;
       x.height = findMax(height(x.left), height(x.right)) + 1;

       // Return new root
       return x;
   }//End of method

   // To left rotate subtree rooted with x
   Node leftRotate(Node x)
   {
       Node y = x.right;
       Node T2 = y.left;

       // Rotation Operation
       y.left = x;
       x.right = T2;

       // Update heights
       x.height = findMax(height(x.left), height(x.right)) + 1;
       y.height = findMax(height(y.left), height(y.right)) + 1;

       // Return new root
       return y;
   }//End of method

   // Returns Balance factor of node N
   int getBalance(Node NN)
   {
       if (NN == null)
           return 0;

       return height(NN.left) - height(NN.right);
   }//End of method

   Node insert(Node n, int k)
   {

       //Perform the normal BST insertion
       if (n == null)
           return (new Node(k));

       if (k < n.key)
           n.left = insert(n.left, k);
       else if (k > n.key)
           n.right = insert(n.right, k);
       // Duplicate keys restricted
       else
           return n;

       //Update height of this ancestor node
       n.height = 1 + findMax(height(n.left), height(n.right));

       //Get the balance factor of this ancestor
       //node to check whether this node became unbalanced
       int balance = getBalance(n);

       // If this node becomes unbalanced, then there are 4 cases
       //Left Left Case
       if (balance > 1 && k < n.left.key)
       {
           System.out.println(\"Left Left Roation Requires (LL Rotation): \" + k);
           return rightRotate(n);
       }          

       // Right Right Case
       if (balance < -1 && k > n.right.key)
       {
           System.out.println(\"Right Right Roation Requires (RR Rotation): \" + k);
           return leftRotate(n);
       }

       // Left Right Case
       if (balance > 1 && k > n.left.key)
       {
           System.out.println(\"Left Right Roation Requires (LR Rotation): \" + k);
           n.left = leftRotate(n.left);
           return rightRotate(n);
       }

       // Right Left Case
       if (balance < -1 && k < n.right.key)
       {
           System.out.println(\"Right Left Roation Requires (RL Rotation): \" + k);
           n.right = rightRotate(n.right);
           return leftRotate(n);
       }

       // return the (unchanged) node pointer
       return n;
   }//End of method

   // To print Pre - order traversal of the tree.
   void preOrderTraversal(Node n)
   {
       if (n != null)
       {
           System.out.print(n.key + \" \");
           preOrderTraversal(n.left);
           preOrderTraversal(n.right);
       }//End of if
   }//End of method

   //Main method
   public static void main(String[] args)
   {
       //Creates AVL Tree class object
       AVLTree mytree = new AVLTree();

       //Constructing tree
       mytree.root = mytree.insert(mytree.root, 50);
       mytree.root = mytree.insert(mytree.root, 10);
       mytree.root = mytree.insert(mytree.root, 70);
       mytree.root = mytree.insert(mytree.root, 25);
       mytree.root = mytree.insert(mytree.root, 32);
       mytree.root = mytree.insert(mytree.root, 5);
       mytree.root = mytree.insert(mytree.root, 7);

       System.out.println(\"Preorder traversal of Tree is : \");
       mytree.preOrderTraversal(mytree.root);
   }//End of main method
}//End of class

Output

Right Right Roation Requires (RR Rotation): 32
Left Left Roation Requires (LL Rotation): 5
Left Right Roation Requires (LR Rotation): 7
Preorder traversal of Tree is :
25 7 5 10 50 32 70