On this page

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced: for every node, the heights of its left and right subtrees differ by at most 1.

Constraints:

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

Brute Force

At every node, compute the height of the left subtree and the height of the right subtree with the max-depth function. If they differ by more than 1, the tree is not balanced. Then recursively check the left and right children the same way.

This recomputes heights again and again: a node deep in the tree has its height calculated once for every ancestor. On a skewed tree that makes it O(n^2).

Optimal Approach: Return -1 for Unbalanced

Compute the height and the balance check in the same pass. Write a helper height(node) that returns:

  • the height of the subtree, if it is balanced, or
  • -1, if the subtree is already unbalanced anywhere.

Steps:

  1. If the node is null, return 0.
  2. Get lh. If it is -1, return -1 right away.
  3. Get rh. If it is -1, return -1.
  4. If abs(lh - rh) > 1, return -1.
  5. Otherwise return 1 + max(lh, rh).

The tree is balanced if the answer at the root is not -1. Using -1 as a signal lets a failure bubble all the way up without any extra recomputation.

Code

class Solution {
public:
int height(TreeNode* node) {
if (node == nullptr) return 0;
int lh = height(node->left);
if (lh == -1) return -1;
int rh = height(node->right);
if (rh == -1) return -1;
if (abs(lh - rh) > 1) return -1;
return 1 + max(lh, rh);
}
bool isBalanced(TreeNode* root) {
return height(root) != -1;
}
};

Complexity

Time: O(n)

Each node is visited once. The brute force version is O(n^2).

Space: O(h)

Recursion stack depth equals the tree height.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The brute force checks the height difference at every node by recomputing heights, which is O of n squared on a skewed tree. The better way is to combine the height and the balance check in one recursion. My helper returns the height if the subtree is balanced and minus one if it is not. If either child returns minus one I return minus one immediately. If the two heights differ by more than one I return minus one. Otherwise I return one plus the max of the heights. The tree is balanced when the root does not return minus one. That visits each node once, so time is O of n, and space is O of h for the recursion."
Next TopicDiameter of Binary Tree