#include
using namespace std;
//--------------------------------------------------------------------------------------------------
class node{
public:
int value;
node* left;
node* right;
};
//--------------------------------------------------------------------------------------------------
node* createNode(int v){
node* n = new node();
n->value = v;
n->left = NULL;
n->right = NULL;
return n;
}
//--------------------------------------------------------------------------------------------------
void insert(node* r, int value){
if (r == NULL) {
r = createNode(value);
}
else{
if (value < r->value)
insert(r->left, value);
else
insert(r->right, value);
}
}
//--------------------------------------------------------------------------------------------------
void inorder(node* root){
if (root != NULL) {
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
//--------------------------------------------------------------------------------------------------
int maxValue(node* root, int v){
int l = 0, r = 0;
if (root != NULL) {
l = maxValue(root->left,v);
r = maxValue(root->right,v);
}
else {
return 1;
}
return r > l ? r : l;
}
//--------------------------------------------------------------------------------------------------
int findHeight(node* root){
if (root == NULL)
return 0;
return max(findHeight(root->left),findHeight(root->right)) + 1;
}
//--------------------------------------------------------------------------------------------------
bool isBalanced(node* r){
int l = findHeight(r->left);
int rght = findHeight(r->right);
if (l < max(0,rght-1) && l > min(0,rght+1))
return true;
else
return false;
}
//--------------------------------------------------------------------------------------------------
node* insertBalancedTree(node* r, int value){
if (isBalanced(r)) {
if (value < r->value)
r->left = insertBalancedTree(r->left, value);
else
r->right = insertBalancedTree(r->right, value);
}
else{
if (value < r->value)
r->left = NULL;
else
r->right = NULL;
}
return r;
}
//--------------------------------------------------------------------------------------------------
void printInOrder(node* root){
if (root != NULL) {
printInOrder(root->left);
cout << root->value << " ";
printInOrder(root->right);
}
}
//--------------------------------------------------------------------------------------------------
int main()
{
node* r = createNode(10);
insert(r,5);
insert(r,15);
insert(r,2);
insert(r,7);
insert(r,12);
insert(r,18);
printInOrder(r);
cout << endl;
cout << "Height of tree : " << findHeight(r) << endl;
bool ans = isBalanced(r);
cout << "Is tree balanced ? " << (ans==true?"Yes":"No") << endl;
r = insertBalancedTree(r, 17);
printInOrder(r);
cout << endl;
bool ans2 = isBalanced(r);
cout << "Is tree balanced ? " << (ans2==true?"Yes":"No") << endl;
return 0;
}