Skip to main content

Balanced Binary Tree

Problem​

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

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
    bool ans;
    map<TreeNode*, int> mp;

   public:
    void traverse(TreeNode* root) {
        if (!root) return;
        traverse(root->left);
        traverse(root->right);
        mp[root] = 0;
        int diff = 0;
        if (root->left) {
            mp[root] = max(mp[root], mp[root->left] + 1);
            diff = mp[root->left] + 1;
        }
        if (root->right) {
            mp[root] = max(mp[root], mp[root->right] + 1);
            diff -= mp[root->right] + 1;
        }
        diff = abs(diff);
        if (diff > 1) ans = false;
    }

    bool isBalanced(TreeNode* root) {
        ans = true;
        traverse(root);
        return ans;
    }
};