# Inserting in an AVL Tree

### Procedure :

• Use the same method used for inserting in a BST.

• Set the height of new nodes to either 1 or 0. (1 used in code below)

• Calculate the height and balance factor of each node.

• If the balance factor is not -1, 0 or 1, the tree is imbalanced.

• Perform required rotation.

``````struct Node *insert(struct Node *ptr, int data) {

if (ptr == NULL) {
// Create a new node and assign required values
struct Node *newNode;
newNode = (struct Node *)malloc(sizeof(struct Node));
newNode -> data = data;
newNode -> left = newNode -> right = NULL;
newNode -> height = 1;
return newNode;
}

if (data < ptr -> data)
ptr -> left = insert(ptr -> left, data);
else if (data > ptr -> data)
ptr -> right = insert(ptr -> right, data);

// Assign height as the max height of left subtree and right subtree
ptr -> height = nodeHeight(ptr);

// Check balance factor and perform rotation
if (balanceFactor(ptr) == 2 && balanceFactor(ptr -> left) == 1)
return LLRotation(ptr);
else if (balanceFactor(ptr) == 2 && balanceFactor(ptr -> left) == -1)
return LRRotation(ptr);
else if (balanceFactor(ptr) == -2 && balanceFactor(ptr -> right) == 1)
return RLRotation(ptr);
else if (balanceFactor(ptr) == -2 && balanceFactor(ptr -> right) == -1)
return RRRotation(ptr);

return ptr;

}``````

Utility Functions :

``````int nodeHeight(struct Node *ptr) {

int leftHeight, rightHeight;
leftHeight = ptr && ptr -> left ? ptr -> left -> height : 0;
rightHeight = ptr && ptr -> right ? ptr -> right -> height : 0;
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

}

int balanceFactor(struct Node *ptr) {

int leftHeight, rightHeight;
leftHeight = ptr && ptr -> left ? ptr -> left -> height : 0;
rightHeight = ptr && ptr -> right ? ptr -> right -> height : 0;
return leftHeight - rightHeight;

}``````

Contributed by Nitin Ranganath

Last updated