#include <iostream>
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;
}