1. public  Node insertToAVL(Node node,int data)
2.     {
3.         if(node == null){
4.             return new Node(data);
5.         }
6.  
7.         if(data < node.data){
8.             node.left = insertToAVL(node.left, data);
9.         }else if(node.data < data){
10.             node.right = insertToAVL(node.right, data);
11.         }
12.  
13.         int lht = height(node.left) , rht = height(node.right);
14.         node.height = Math.max(lht, rht)+1;
15.         int diff = lht - rht;
16.  
17.         Node newRoot = node;
18.         if(diff > 1){ // left
19.             if(data < node.left.data){ // LL
20.                 newRoot = rightRotate(node);
21.             }else if(data > node.left.data){ // LR
22.                 node.left = leftRotate(node.left);
23.                 newRoot = rightRotate(node);
24.             }
25.         }else if(diff < -1){ // right
26.             if(data < node.right.data){ // RL
27.                 node.right = rightRotate(node.right);
28.                 newRoot = leftRotate(node);
29.             }else if(data > node.right.data){ // RR
30.                newRoot = leftRotate(node);
31.             }
32.         }
33.  
34.         return newRoot;
35.     }
36.  
37.     public int height(Node node){
38.         if(node == null){
39.             return -1;
40.         }else{
41.             return node.height;
42.         }
43.     }
44.  
45.     public Node leftRotate(Node a){
46.         Node b = a.right;
47.         Node t2 = b.left;
48.  
49.         b.left = a;
50.         a.right = t2;
51.  
52.         a.height = Math.max(height(a.left), height(a.right))+1;
53.         b.height = Math.max(height(b.left), height(b.right))+1;
54.         return b;
55.     }
56.  
57.     public Node rightRotate(Node a){
58.         Node b = a.left;
59.         Node t2 = b.right;
60.  
61.         b.right = a;
62.         a.left = t2;
63.  
64.         a.height = Math.max(height(a.left), height(a.right))+1;
65.         b.height = Math.max(height(b.left), height(b.right))+1;
66.         return b;
67.     }