Back to solutions

Balanced Binary Tree

EasyBinary Trees

Return true if a binary tree is height-balanced, meaning every node's two subtrees differ in height by at most one.

Open problem
Constraints
  • 0 <= nodes <= 5000
  • -10^4 <= Node.val <= 10^4

Post-order height with early exit

Time O(n)Space O(h)

Compute subtree heights bottom-up; return a sentinel of -1 as soon as any node is unbalanced so the whole tree fails in a single pass.

#include <bits/stdc++.h>
using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

int height(TreeNode* node) {
    if (!node) return 0;
    int l = height(node->left);
    if (l == -1) return -1;
    int r = height(node->right);
    if (r == -1) return -1;
    if (abs(l - r) > 1) return -1;
    return 1 + max(l, r);
}

bool isBalanced(TreeNode* root) { return height(root) != -1; }