Please pay attention to the prompt: C++ AVL Tree is a Binary Search Tree that al
ID: 3904905 • Letter: P
Question
Please pay attention to the prompt:
C++
AVL Tree is a Binary Search Tree that allows Balance Factor of each node to be in the range -1 to 1 (n>=0). Implement a function that takes as input a root node of a Binary Search Tree. This function checks if the BST is a AVL Tree or not.
We have defined the following node C++ Node class for you:
Function to code:
The first input in test cases are nodes of a tree which are inserted in that order. You don't need to implement insert. You have access to the root of the constructed Binary Search Tree. The second line is input n. Return true if the BST is AVL and False if not.
Examples:-
1. Numbers: - 5 2 15 16 9 11 14 ;
Tree:- 5
/
2 15
/
9 16
11
14
Balance Factor of tree = left subtree height – right subtree height = -3
Therefore, this BST is not an AVL Tree.
Hint: Use a Height function to calculate height of a tree at given node.
Sample Input 1:
Sample Output 1:
Sample Input 2:
Sample Output 2:
Sample Input 3:
Sample Output 3:
Sample Input 4:
Sample Output 4:
Sample Input 5:
Sample Output 5:
Sample Input 6:
Sample Output 6:
Sample Input 7:
Sample Output 7:
Sample Input 8:
Sample Output 8:
Thanks!
Explanation / Answer
Solution:- For this problem, Basically we have to implement the fuction to calculate the height of a BST.
==============CODE====================
if(root == NULL)
return 0;
return 1 + max(height(root->left), height(root->right));
}
//The function isAVL() will return TRUE if the BST is HEIGHT BALANCED else will return false
bool isAVL(Node *root) {
int lHeight;
int rHeight;
if(root == NULL)
return 1;
lHeight = height(root -> left);
rHeight = height(root->right);
if( abs(lh-rh) <= 1 && isAVL(root->left) && isAVL(root->right))
return 1;
/* If we reach here then tree is not height-balanced */
return 0;
}
=================CODE ENDS=================
Note:- Please upvote if it helped, else do comment on the part you need more explanation to, I'll be happy to help.
Thanks!!