An AVL tree is a binary search tree which has the following properties:-

a. The sub-trees of every node differ in height by at most one.

b. Every sub-tree is an AVL tree.

c. Each node in the AVL Tree possesses any one of the following properties:

d. A node is called left heavy, if the largest path in its left sub tree is one level larger than the largest path of its right sub tree.

e. A node is called right heavy, if the largest path in its right sub tree is one level larger than the largest path of its left sub tree.

f. The node is called balanced, if the largest paths in both the right and left sub trees are equal.

Consider the Example