determine if a binary tree is height-balanced

PROBLEM :

Given a binary tree, find if it is height balanced or not.  A tree is heigh balanced if difference between heights of left and right subtrees is not more than one for all nodes of tree.    Expected time complexity is O(n).

A height balanced tree
        1
     /     \
   10      39
  /
5

An unbalanced tree
        1
     /  
   10
  /
5



Input:
The task is to complete the method which takes one argument, root of Binary Tree. The struct Node has a data part which stores the data, pointer to left child and pointer to right child.
There are multiple test cases. For each test case, this method will be called individually.

Output:
The function should return true if tree is height balanced, else false.

Constraints:
1 <=T<= 30
1 <=Number of nodes<= 100
1 <=Data of a node<= 1000


--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(o(n^2))
--------------------------------------------------------------------------------

/* A binary tree node structure
struct Node {
    int data;
    struct Node* left, * right;
}; */

// This function should return tree if passed  tree
// is balanced, else false.  Time complexity should
//  be O(n) where n is number of nodes in tree

int height(struct Node *) ;

bool isBalanced(struct Node *root)
{
    if(root==NULL||(root->left==NULL&&root->right==NULL))
        return true ;
     
    int Lheight ,Rheight ;
    Lheight=height(root->left) ;
    Rheight=height(root->right) ;
 
    if((abs(Lheight-Rheight)<2)&&isBalanced(root->left)&&isBalanced(root->right))
        return true ;
    else
        return false ;
 
}

int height(struct Node *root)
{
    if(root==NULL)
    return 0 ;
 
    int L,R ;
    L=height(root->left) ;
    R=height(root->right) ;
 
    return(L>R?(L+1):(R+1)) ;
}

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :(o(n))
--------------------------------------------------------------------------------

/* A binary tree node structure
struct Node {
    int data;
    struct Node* left, * right;
}; */

// This function should return tree if passed  tree
// is balanced, else false.  Time complexity should
//  be O(n) where n is number of nodes in tree

int CheckBalence(struct Node *,bool*) ;
bool isBalanced(struct Node *root)
{
    if(root==NULL)
        return true ;
   
    if(root->left==NULL&&root->right==NULL)
        return true ;
   
    bool state=true ;
    int bf=CheckBalence(root,&state) ;
    if(state)
        return true ;
    else
        return false ;
}

int CheckBalence(struct Node *root,bool *state)
{
    if((*state)==false)
        return 1 ;
    if(root==NULL)
        return 0 ;
    if(root->left==NULL&&root->right==NULL)
        return 1 ;
       
    int l,r ;
    l=CheckBalence(root->left,&(*state)) ;
    r=CheckBalence(root->right,&(*state)) ;
   
    if(l-r>=-1&&l-r<=1)
      {
          (*state)=true ;
          return l>r?l+1:r+1 ;
      }
    else
     {
         (*state)=false ;
         return INT_MAX ;
     }
}

---------------------------------------------------------------------------------