AVL Deletion
This lesson will cover the deletion operation in AVL trees, discussing all the four deletion cases.
Deletion in AVL Tree
Deletion is similar to AVL’s insertion operation with just one exception:
The deletion operation adds an extra step after the insertion method’s rotation and balancing of the first unbalanced node.
After fixing the first unbalanced node through rotations, start moving up and fix the next unbalanced node. Keep on fixing the unbalanced nodes until you reach the root.
Steps for Deletion
The following are the detailed steps for removing value from AVL Trees.
Step 1: Delete currentNode
Delete the currentNode in the same way as we did in BST deletion. At this point, the tree will become unbalanced, and we would need to perform some kind of rotation (left or right) to rebalance the tree.
Step 2: Traverse Upwards
Start traversing from currentNode upwards till you find the first unbalanced node.
Let’s look at some of the terms 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
Step 3: Rebalance the Tree
To rebalance the tree, we will perform rotations on the subtree where U is 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.
After performing a successful rotation for the first unbalanced Node U, traverse up and find the next unbalanced node and perform the same series of operations to balance. Keep on balancing the unbalanced nodes from first Node U to ancestors of Node U until we reach the root. After that point, we will have a fully balanced AVL Tree.
Case 1: LeftLeft
Level up your interview prep. Join Educative to access 80+ handson prep courses.