Problem overview
The method isBalanced receives the root of a binary tree and returns true when the tree is height-balanced. That means that at every node, the heights of the left and right subtrees differ by at most 1. The height of a tree is the number of nodes on its longest path from the top down to a leaf, an empty tree has height 0, and an empty tree is balanced. The lesson provides the TreeNode struct, with an int val and the pointers left and right.
In the first example, the root 3 has the left subtree 9 (height 1) and the right subtree 20, 15, 7 (height 2). They differ by 1, and the other nodes are balanced too, so the answer is true. In the second example, [1,2,2,3,3,NULL,NULL,4,4], the root's left subtree has height 3 and its right subtree has height 1: they differ by 2, so the answer is false.
The third example, [1,2,2,3,NULL,NULL,3,4,NULL,NULL,4], is the instructive one. The root is fine, since both of its subtrees have height 3. But the left 2 has a left subtree of height 2 and an empty right subtree of height 0, and the rule fails there. Checking only the root is never enough.
Approach: compute heights from the bottom up
A direct solution writes a height function and, for every node, compares the heights of its two subtrees. That recomputes the same heights again and again: each node's height is measured once for every ancestor above it, which can take O(n²) time on a long, thin tree.
The faster idea is to find each height once, from the bottom up, and to check the rule at the same moment. The recursive helper height returns the height of the tree under a node when that tree is balanced, and the special value -1 when some node inside it breaks the rule. A real height is never negative, so -1 can't be mistaken for one.
Each call asks its two children first. If either one reports -1, the answer is -1 straight away: part of the tree is unbalanced, so the whole tree is. Otherwise the call compares the two heights, returns -1 if they differ by more than 1, and returns 1 + max(left, right) if all is well. Every node runs this code on the way back up, so the rule is checked at every node. isBalanced then only asks whether height(root) is different from -1.
On the first example, height(9) is 1, height(20) is 2 and height(root) is 3, so the answer is true. On the second example, the left 2 has height 3 and the right 2 has height 1, so height(root) is -1. On the third example, height(left 2) is already -1, and that -1 travels up to the root.
Step by step
- Write
isBalancedin terms of the helper: return whetherheight(root)is not -1. The helper comes next. - Write the helper's signature.
heightreturns anintand takes aTreeNode* node. It goes aboveisBalancedin the class. - Handle the empty tree. If
nodeisnullptr(!node), return 0. This is both the height of an empty tree and the base case that stops the recursion past a leaf. - Get the left height with a recursive call on
node->left, and store it inleftHeight. - Pass the signal up. If
leftHeightis -1, return -1 without even looking at the right subtree. - Get the right height the same way, from
node->right, intorightHeight. A missing child gives 0. - Check the right result for -1 too. Don't skip it: -1 would otherwise pass as a height, and it differs from an empty side's 0 by only 1.
- Check this node. If
abs(leftHeight - rightHeight) > 1, return -1.absdrops the sign, so it doesn't matter which side is taller. - Return the height: 1 for the node itself plus
max(leftHeight, rightHeight), because the longest path goes through the taller subtree.
The solution in C++
class Solution {
public:
int height(TreeNode* node) {
if (!node) {
return 0;
}
int leftHeight = height(node->left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = height(node->right);
if (rightHeight == -1) {
return -1;
}
if (abs(leftHeight - rightHeight) > 1) {
return -1;
}
return 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return height(root) != -1;
}
};
C++ details worth knowing:
- A pointer in a condition.
!nodeis true whennodeis a null pointer, the same asnode == nullptr. The struct's constructor setsleftandrighttoNULLfor a leaf. - Dereferencing null is undefined. The base case must come first:
node->lefton a null pointer is undefined behaviour and typically crashes. - The helper is a member function. It doesn't use
this, but writing it inside the class keeps it withisBalancedand letsisBalancedcall it without extra setup. - Recursion depth. The tree is at most 800 levels deep, so the recursion is shallow enough for the call stack. A chain of 800 nodes is unbalanced and returns
false, and a complete tree of 5000 nodes returnstrue.
Complexity
Time: O(n). Each node is visited once, and each visit does constant work: two comparisons and one subtraction. Returning early on -1 can only make the run shorter.
Space: O(h). No extra data structure is built. The recursion uses one stack frame per level, so it needs memory proportional to the tree's height h, which is at most 800 here.
Edge cases and common mistakes
- An empty tree.
height(nullptr)is 0, which is not -1, so an empty tree is balanced. - A single node. Both children are empty, with heights 0 and 0, so it is balanced with height 1.
- Checking only the root. The third example has a balanced root and an unbalanced node below it. The answer is
false. - Unbalanced at a node with one short side. A chain such as
[1, 2, NULL, 3](each node only a left child) returnsfalse: at the root, the left subtree has height 2 and the right one has height 0. - Forgetting the -1 check after the right subtree. Take the chain
[1, NULL, 2, NULL, 3, NULL, 4], where each node has only a right child. The node 2 is unbalanced, so its height is -1. Without the check, the root compares its empty left side, 0, with -1, sees a difference of only 1 and returns 1, whichisBalancedreads as balanced. With the check,height(root)is -1 and the answer isfalse.
Testing
[3,9,20,NULL,NULL,15,7]givestrue.[1,2,2,3,3,NULL,NULL,4,4]givesfalse.[1,2,2,3,NULL,NULL,3,4,NULL,NULL,4]givesfalse.- An empty tree gives
true. [1]givestrue.[1,2]givestrue.[1,2,NULL,3]givesfalse.[1,NULL,2,NULL,3,NULL,4]givesfalse.
