Question

Write a C++ program that checks whether a binary search tree is an AVL. The input is an arbitrary binary search tree, and the output is binary, so either true or false.

Answer 1

//For checking given tree is AVL or not we need to find left height and right height of each node and difference between left and right height should not be more than 1.

//AVL is balanaced binary serach tree.

//height() is used to find height of given node
int height(nod* node) 
{ 
   if(node == NULL)
      return 0;
   return 1 + max(height(node->left), height(node->right));
}

//AVL () :Check given BST is AVL or not.

bool AVL(nod *root) {
   int lh;
   int rh;
   if(root == NULL)
      return 1;
   lh = height(root->left); // left height
   rh = height(root->right); // right height
   if(abs(lh-rh) <= 1 && AVL(root->left) && AVL(root->right)) 
       return true;
   return false;
}