110. Balanced Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    pair<int, bool> solve(TreeNode* root)
    {
        if(root == NULL)
        {
            return {0, true};
        }

        pair<int, bool> left = solve(root -> left);
        pair<int, bool> right = solve(root -> right);

        pair<int, bool> ans;

        //finding the height of that subtree
        ans.first = max(left.first, right.first) + 1;

        //checking for balanced
        bool diff = abs(left.first - right.first) <= 1;


        ans.second = left.second && right.second && diff;

        return ans;
    }


    bool isBalanced(TreeNode* root) {
       return  solve(root).second;
    }
};