Step 1: BST Insertion

• Compare the new node’s key with the current node’s key.
• If the new key is smaller, recursively insert it into the left subtree.
• If the new key is larger, recursively insert it into the right subtree.
• If the current node is null (empty), insert the new node there.

Step 2: Update Height and Balance Factor: After inserting the new node, traverse back up the tree from the inserted node toward the root. At each node encountered:

1. • Update the node’s height. The height of a node is 1 + the maximum of the heights of its left and right children.
   • Calculate the balance factor of the node: BF = height(left subtree) – height(right subtree).

Step 3:Check for Imbalance and Rotate (if necessary): If the balance factor of any node becomes -2 or 2, the tree is unbalanced. Perform appropriate rotations to restore balance:

1. • BF = 2:
     • Left-Left Case: Perform a single right rotation on the imbalanced node.
     • Left-Right Case: Perform a left-right rotation (a left rotation on the left child, followed by a right rotation on the imbalanced node).
   • BF = -2:
     • Right-Right Case: Perform a single left rotation on the imbalanced node.
     • Right-Left Case: Perform a right-left rotation (a right rotation on the right child, followed by a left rotation on the imbalanced node).

When an insertion or deletion causes this balance factor to exceed 1, rotations are performed to restore balance. There are four types of rotations: Left Rotation , Right Rotation , Left-Right Rotation  , and Right-Left Rotation .