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:
- If the node is
null, return 0. - Get
lh. If it is -1, return -1 right away. - Get
rh. If it is -1, return -1. - If
abs(lh - rh) > 1, return -1. - 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
Each node is visited once. The brute force version is O(n^2).
Recursion stack depth equals the tree height.