C++: Balanced Binary Tree

Thought Process

To determine if a binary tree is balanced, we can use a recursive approach. A tree is balanced if the height difference between the left and right subtrees of every node is at most '1'. We calculate the height of each subtree recursively and check if the absolute difference in heights exceeds '1'. If it does, the tree is unbalanced. This approach ensures that we traverse the tree efficiently while checking the balance condition. 

/**
 * 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:
    bool isBalance = true;

    int height(TreeNode *root){

        if(root==NULL)
            return 0;

        int htLeft = height(root->left);
        int htRight = height(root->right);

        if(abs(htLeft-htRight)>1)
            isBalance = false;

        return 1+max(htLeft,htRight);
    }
    bool isBalanced(TreeNode* root) {
        
        int x = height(root);
        return isBalance;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree (h). In the worst case (a skewed tree), the space complexity is O(n).

Code copied!