Adding a Node in AVL Tree

Perform standard BST insert. Let the newly inserted node be w. After insertion find BF (balance factor for each node in new tree)

Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.

There can be 4 possible cases that needs to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements:
a) y is left child of z and x is left child of y (Left Left Case)
b) y is left child of z and x is right child of y (Left Right Case)
c) y is right child of z and x is right child of y (Right Right Case)
d) y is right child of z and x is left child of y (Right Left Case)

Re-balance the tree by performing appropriate rotations on the subtree rooted with z.

a)Left Left Case – Perform Right rotation at Z
b) Left Right Case – Perform Left rotation at Y and Right rotation at Z
c) Right Right Case – Perform Left rotation at Z
d) Right Left Case – Perform Right rotation at Y and Left rotation at Z

Click the link to watch the video ADDING Node to AVL tree