AVL Insertion
This lesson will cover the insertion operation in AVL trees, discussing all four insertion cases.
Insertion in AVL Tree
Insertion for an AVL tree follows the same steps that we covered in BST insertion.
The main step comes after insertion when the tree gets unbalanced.
To rebalance the tree, we need to perform some kind of rotation (left or right). But before getting into the deeper concepts that’ll be a mess for you to understand at this point, let’s slowly cover one case at a time.
Let’s look at some of the terms which we will be using while rebalancing the tree.
 Node U – an unbalanced node
 Node C – child node of node U
 Node G – grandchild node of node U
Insertion Cases
To rebalance the tree, we will perform rotations on the subtree with Node U as being the root node.
There are two types of rotations:
 left
 right
We came across four different scenarios based on the arrangements of Nodes U, C and, G.

LeftLeft: Node C is the leftchild of Node U, and Node G is the leftchild of Node C.

LeftRight: Node C is the leftchild of Node U, and Node G is the rightchild of Node C.

RightRight: Node C is the rightchild of Node U, and Node G is the rightchild of Node C.

RightLeft: Node C is the rightchild of Node U, and Node G is the leftchild of Node C.
$$$$
Case 1: LeftLeft
Level up your interview prep. Join Educative to access 80+ handson prep courses.