Problem Statement

Given a binary tree, determine if it is height-balanced.

Height-balanced binary tree : is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Example :

`Input : 1 / \ 2 3

Return : True or 1

Input 2 : 3 / 2 / 1

Return : False or 0 Because for the root node, left subtree has depth 2 and right subtree has depth 0. Difference = 2 > 1.`

Problem Link

Balanced Binary Tree - InterviewBit

Reference Link

How to determine if a binary tree is height-balanced? - GeeksforGeeks

Code

int solve(TreeNode* root,int &height) 
 {
     int lh = 0,rh =0;
     int lst = 0,rst = 0;
     
     if(!root)
     {
         height = 0;
         return 1;
     }
     
     
     
     lst = solve(root->left,lh);
     rst = solve(root->right,rh);
     
     height = 1+ max(lh,rh);
     
     if(abs(lh-rh)>1)
     return 0;
     
     return lst&&rst;
     
     
 }
int Solution::isBalanced(TreeNode* root) {
    
    int height = 0;
    
    return solve(root,height);
}

Another way

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
int height(TreeNode* A) {
    if(A==NULL) {
        return 0;
    }
    
    return 1 + max(height(A->left),height(A->right));
    
    
}
int Solution::isBalanced(TreeNode* A) {
    
    if(A==NULL) {
        return 1;
    }
    
    if(!A->left&&!A->right) {
        return 1;
    }
    
    int lt = height(A->left);
    int rt = height(A->right);
    
    return abs(lt-rt) <= 1 && isBalanced(A->left) && isBalanced(A->right);
}