struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


/**
 * Calculate the height of the tree begin with TreeNode
 * @param  n        Root node to measure the height
 * @param  balanced Indicate if the tree is balanced, if not no need to calculate anymore
 * @return          The height of tree or -1 if tree is not balanced
 */
int heightOf(TreeNode *n, bool& balanced) {
    if (n == NULL) {
        return 0;
    }
    // process left/right child, 
    // stop process when tree is not balanced
    int lh = heightOf(n->left, balanced);
    if (!balanced) return -1; 

    int rh = heightOf(n->right, balanced);
    if (!balanced) return -1;

    // test if current node is balanced,
    // if not, set balanced to false, and stop process
    if (lh-rh > 1 || rh-lh > 1) {
        balanced = false;
        return -1;
    }

    //return max height of left/right height plus 1 as height of current node
    return (lh>rh? lh: rh)+1;
}


bool isBalanced(TreeNode *root) {
    bool balanced = true;

    heightOf(root, balanced);

    return balanced;
}