Balanced Binary Tree

Problem

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

Constraints

• The number of nodes in the tree is in the range [0, 5000].
• -104 <= Node.val <= 104

Solution

The problem Balanced Binary Tree can be solved by recursively checking if the left and right subtrees are balanced and the depth of the two subtrees does not differ by more than one.

Implementation

/**
 * 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:
    int maxDepth(TreeNode *root, bool &is_balanced)
    {
        if (!is_balanced || root == NULL)
            return 0;

        int left = maxDepth(root->left, is_balanced);
        int right = maxDepth(root->right, is_balanced);

        is_balanced = is_balanced && abs(left - right) <= 1;
        return max(left, right) + 1;
    }

    bool isBalanced(TreeNode *root)
    {
        bool is_balanced = true;
        maxDepth(root, is_balanced);
        return is_balanced;
    }
};