Problem overview
The method isBalanced receives the root of a binary tree and returns true when the tree is height-balanced: 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 counts as balanced. The lesson provides the TreeNode class, with an int val and two TreeNode fields, left and right.
The tree [3, 9, 20, null, null, 15, 7] (level order, null for a missing child) is balanced. At the root, the left subtree (just the 9) has height 1 and the right subtree (20, 15, 7) has height 2, a difference of 1. At the 20, both subtrees have height 1. The tree [1, 2, 2, 3, 3, null, null, 4, 4] is not: at the root the left subtree has height 3 and the right one has height 1.
The rule must hold at every node. In [1, 2, 2, 3, null, null, 3, 4, null, null, 4] the root is fine, with both subtrees of height 3, yet the left 2 has a left subtree of height 2 and an empty right subtree of height 0. The answer is false.
Approach: compute heights from the bottom up and check as you go
The direct way is to write a height function and, at each node, compare the heights of its two subtrees, then do the same for every node below. That measures the same subtrees again and again: each node's height is recomputed for every ancestor above it. On a tall, thin tree this adds up to far more than O(n) work.
The fix is to find each subtree's height once, from the bottom up, and to check the rule at the same moment. A recursive helper height(node) returns:
- the height of the tree under
node, if every node in it satisfies the rule; - or
-1as soon as it finds a node that breaks the rule.
A real height is never negative, so -1 can't be mistaken for one. It is a signal meaning "unbalanced somewhere in here", and every caller passes it up unchanged. The answer is whether height(root) is not -1.
Here is what the helper returns for each node of the three examples, in the order the calls finish (children before their parent):
example 1
node 9: left 0, right 0 -> 1
node 15: left 0, right 0 -> 1
node 7: left 0, right 0 -> 1
node 20: left 1, right 1 -> 2
node 3: left 1, right 2 -> 3
example 2
node 4: left 0, right 0 -> 1
node 4: left 0, right 0 -> 1
node 3: left 1, right 1 -> 2
node 3: left 0, right 0 -> 1
node 2: left 2, right 1 -> 3
node 2: left 0, right 0 -> 1
node 1: left 3, right 1 -> -1
example 3
node 4: left 0, right 0 -> 1
node 3: left 1, right 0 -> 2
node 2: left 2, right 0 -> -1
node 1: left subtree unbalanced -> -1
In the third example the left 2 returns -1, so the root returns -1 at once without looking at its right subtree.
Step by step
- Write
isBalanced's body first: return whetherheight(root) != -1. - Write the helper's signature above it: an
intmethodheighttaking aTreeNode node. - Base case. If
node == null, return 0. An empty tree has height 0 and is balanced; this also stops the recursion past a leaf. - Get the left height with a recursive call on
node.leftand store it inleftHeight. Trust the recursion to return a height or-1. - If
leftHeight == -1, return -1 right away. An unbalanced part makes the whole tree unbalanced, so there is no need to look at the right side. - Do the same for
node.rightand store the result inrightHeight. A missing child gives 0 thanks to the base case. - If
rightHeight == -1, return -1. Don't skip this check: otherwise-1would pass for a height, and it differs from an empty side's 0 by only 1. - Check this node: if
Math.abs(leftHeight - rightHeight) > 1, return -1. Every node runs this on its way back up, so the rule is enforced everywhere, not only at the root.Math.absdrops the sign, so it doesn't matter which side is taller. - Return the height: 1 for the node itself plus
Math.max(leftHeight, rightHeight), because the longest path goes through the taller subtree.
The solution in Java
class Solution {
int height(TreeNode node) {
if (node == null) {
return 0;
}
int leftHeight = height(node.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = height(node.right);
if (rightHeight == -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return 1 + Math.max(leftHeight, rightHeight);
}
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
}
Java details:
- Methods can be written in any order.
isBalancedcallsheight, which is declared above it, but Java would accept the other order too. - A
nullchild is a normal value. Object fields default tonull, so a leaf hasleft == nullandright == null. The base case handles it, and nothing in the method dereferences anull. The empty tree,root == null, returnstrue. - Comparing with
==is fine here.leftHeightis a primitiveint, not anIntegerobject, so== -1compares values. - Recursion depth. The recursion goes as deep as the tree. The lesson allows up to 800 levels, which Java's default stack handles easily; a chain of 800 nodes runs without trouble.
Complexity
Time: O(n). Each node is visited at most once, and each visit does constant work: two comparisons, one subtraction and a Math.max. When a -1 shows up, the method stops visiting further nodes early.
Space: O(h) for a tree of height h, because the recursion keeps one call open per level. It is O(n) for a chain and about O(log n) for a well-balanced tree.
Edge cases and common mistakes
- The empty tree. It has height 0 and is balanced, so
isBalanced(null)returnstrue. - A single node. Both subtrees are empty, so it is balanced.
- Checking only the root. The third example has a root with two subtrees of equal height and is still unbalanced. The rule applies at every node.
- Forgetting to pass the signal up. Without the two
== -1checks, a child's-1would be treated as a height. For a node whose other side is empty (height 0), the difference is 1, and the node would look balanced. - A chain of three. A root with only a left child that has its own left child,
[1, 2, null, 3], is not balanced: at the root, the heights are 2 and 0.
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: the heights at the root are 1 and 0.[1, 2, null, 3]givesfalse.
