C++. Test if a Tree is Balanced Use the given Tree class and implement a functio
ID: 3605107 • Letter: C
Question
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.
Please MAKE SURE TO CLEARLY SHOW THE CODING. AND YOUR OUTPUT.
#include <iostream>
using namespace std;
template<class ItemType>
class Tree {
private:
Tree<ItemType> * left;
Tree<ItemType> * 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;
}
Explanation / Answer
#include <iostream>
using namespace std;
template<class ItemType>
class Tree {
private:
Tree<ItemType> * left;
Tree<ItemType> * 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);
}
}
}
int getHeight() {
int leftHeight = 0, rightHeight =0;
if(left != NULL) {
leftHeight = left->getHeight();
}
if(right != NULL) {
rightHeight = right->getHeight();
}
if(leftHeight > rightHeight) {
return leftHeight + 1;
} else {
return rightHeight + 1;
}
}
bool isBalanced(){
if(left !=NULL && !left->isBalanced()) {
return false;
}
if(right !=NULL && !right->isBalanced()) {
return false;
}
int leftHeight = 0, rightHeight =0;
if(left != NULL) {
leftHeight = left->getHeight();
}
if(right != NULL) {
rightHeight = right->getHeight();
}
return (abs(leftHeight - rightHeight) <= 1);
}
};
int main() {
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.