Balanced Binary Tree

LeetCode #110

Description:

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 depth of the two subtrees of every node never differ by more than 1.

Example:

Note

Idea:

return either -1 (inbalanced) or the height of the tree(subtree).

• left subtree and right subtree both need to be balanced. If one is not balanced, return -1.
• Then also compare the the height of left and right tree.
• If all good, return the depth at this node.

Code:

class Solution {
public:
    bool isBalanced(TreeNode* root) {

        if(balancedHeight(root)==-1)
            return false;
        else
            return true;
    }

    int balancedHeight(TreeNode *root){
        if(root==NULL) return 0;

        int left_depth = balancedHeight(root->left);
        int right_depth = balancedHeight(root->right);

        if(left_depth==-1 || right_depth==-1|| abs(left_depth-right_depth)>1) return -1;

        return max(left_depth, right_depth) + 1;        
    }
};