Balanced Tree Check

A binary tree is height-balanced if, for every node in the tree, the difference in heights of the left and right subtrees is no more than 1.

Approach:

We use a post-order traversal where, at each node, we first calculate the heights of the left and right subtrees, check the balance condition, and then propagate the height upwards. This ensures that we check each node only once, achieving a linear time complexity.

The function solve(Node* root) returns a pair:

• First element: true/false indicating if the subtree rooted at root is balanced.
• Second element: The height of the subtree.

?? View Complete Code ??

pair<bool, int>solve(Node* root){
        
        if(root == NULL){
            pair<bool,int>p = make_pair(true, 0);
            return p;
        }
        
        pair<bool, int>left = solve(root->left);
        pair<bool, int>right = solve(root->right);
        
        bool condn = abs(left.second - right.second) <= 1;
        
        pair<bool, int>ans;
        ans.second = max(left.second, right.second) + 1;
        
        if(left.first && right.first && condn){
            ans.first = true;
            ans.second = max(left.second, right.second) + 1;
        }
        else{
            ans.first = false;
        }
        
        return ans;
        
    }

    bool isBalanced(Node *root)
    {
        return solve(root).first;
    }        

Explanation:

• Base case: If the node is NULL, the tree is balanced with a height of 0.
• Recursive case: Recursively check the left and right subtrees.Compute the height difference and check if it is more than 1. If both left and right subtrees are balanced and the current node satisfies the height difference condition, mark the current subtree as balanced.
• Final Result: The result will return true if the tree is balanced and false if it is unbalanced.

Time Complexity: O(N)

Space Complexity: O(H)

?? GitHub Repository ??