Check Binary Tree is balanced or not
/***
4.1 Implement a function to check if a binary tree is balanced. For the purposes of
this question, a balanced tree is defined to be a tree such that the heights of the
two subtrees of any node never differ by more than one.
***/
#include<iostream>
using namespace std;
struct node {
node *left;
node *right;
};
bool isBalanced(node *root) {
if(getheight(root) != -1)
return true;
else false;
}
int getheight(node *n) {
int d;
if(n->left == nullptr || n->right == nullptr) {
return 0;
}
if(getheight(n->left) == -1 || getheight(n->right) == -1)
return -1;
d = getheight(n->left) - getheight(n->right);
if(d > 1 || d < -1) return -1;
else return max(getheight(n->left), getheight(n->right)) + 1;
}
4.1 Implement a function to check if a binary tree is balanced. For the purposes of
this question, a balanced tree is defined to be a tree such that the heights of the
two subtrees of any node never differ by more than one.
***/
#include<iostream>
using namespace std;
struct node {
node *left;
node *right;
};
bool isBalanced(node *root) {
if(getheight(root) != -1)
return true;
else false;
}
int getheight(node *n) {
int d;
if(n->left == nullptr || n->right == nullptr) {
return 0;
}
if(getheight(n->left) == -1 || getheight(n->right) == -1)
return -1;
d = getheight(n->left) - getheight(n->right);
if(d > 1 || d < -1) return -1;
else return max(getheight(n->left), getheight(n->right)) + 1;
}
Comments
Post a Comment