What is an AVL tree? Explain how a node can be inserted into an AVL tree. 

Ans:
AVL Tree
An AVL tree is a binary tree in which the difference in heights between the left and
the right subtree is not more than one for every node.
We can insert a node into an AVL tree by using the insertion algorithm for binary
search trees in which we compare the key of the new node with that in the root and
then insert the new node into the left subtree or right subtree depending on whether
it is less than or greater than that in the root. Insertion may or may not result in
change in the height of the tree. While inserting we must take care that the balance
factor of any node not changes to values other than 0, 1 and -1. A tree becomes
unbalanced if and only if
(i) The newly inserted node is a left descendant of a node that previously had a
balance of 1.
(ii) The newly inserted node is a right descendent of a node that previously had a
balance of -1.
If the balance factor of any node changes during insertion than one of the subtree is
rotated one or more times to ensure that the balance factor is restored to correct
values.