C++.

Test if a Tree is Balanced

Use the given Tree class and implement a function to test if the binary tree is balanced or not.

An empty tree is height-balanced. A non-empty binary tree T is balanced if:

1) Left subtree of T is balanced

2) Right subtree of T is balanced

3) The difference between heights of left subtree and right subtree is not more than 1.

#include using namespace std;

template class Tree { private: Tree * left; Tree * right; ItemType data; public: Tree(ItemType _data){left = NULL; right = NULL; data = _data;} void insert(ItemType _data){ if( _data > data){ if(right == NULL){ right = new Tree(_data); }else{ right->insert(_data); } }else{ if(left == NULL){ left = new Tree(_data); }else{ left->insert(_data); } } } bool isBalanced(){ // Implement this Function } };

int main() { return 0; }