An empty tree is height balanced. A non empty binary tree T is balanced if
- Left subtree of T is balanced
- Right subtree of T is balanced
- The difference between heights of left subtree and right subtree is not more than one. This above height balancing scheme is used in…