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, and an empty tree has height 0 and is balanced. The lesson provides the TreeNode class, whose nodes have val, left and right, with None for a missing child.
The tree [3, 9, 20, None, None, 15, 7] (level order, None for a missing child) is balanced. At the root the left subtree (just the 9) has height 1 and the right subtree (20 with 15 and 7) has height 2, a difference of 1. At the 20 both sides have height 1.
The tree [1, 2, 2, 3, 3, None, None, 4, 4] is not balanced. At the root the left subtree has height 3 and the right subtree has height 1.
The tree [1, 2, 2, 3, None, None, 3, 4, None, None, 4] is not balanced either, and it is the instructive one. Both subtrees of the root have height 3, so the root is fine. But the left 2 has a left subtree of height 2 (the 3 and the 4 under it) and an empty right subtree of height 0. The rule must hold at every node, not only at the root.
The lesson asks for O(n) time, visiting each node once.
Approach: compute heights from the bottom up and carry a failure signal
The direct way writes a height function and, at every node, calls it on both children to compare them. That measures the same subtrees again and again: the height of a deep subtree is recomputed for every node above it. On a long chain of nodes the repeated work adds up to far more than one visit per node.
The better way finds each subtree's height once, from the bottom up, and checks the rule at the same time. A recursive helper height returns the height of the tree under a node, or -1 as 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 means "unbalanced somewhere in here". Once a subtree reports -1, the node above passes it up at once without looking further.
Running the helper on the example trees gives these heights:
| tree | height(root) | isBalanced |
|---|---|---|
[3, 9, 20, None, None, 15, 7] | 3 | True |
[1, 2, 2, 3, 3, None, None, 4, 4] | -1 | False |
[1, 2, 2, 3, None, None, 3, 4, None, None, 4] | -1 | False |
[] (an empty tree) | 0 | True |
[1, 2] | 2 | True |
[1, 2, None, 3] | -1 | False |
In the third tree, the call on the left 2 already returns -1 and the call on the right 2 also returns -1, so the root never compares the two subtrees: the signal travels up.
Step by step
- In
isBalanced, return whetherself.height(root)is not-1. - Write the helper's
defline: a methodheighttakingselfand anode. It is written aboveisBalanced. - Base case: if
nodeisNone(not node), return 0. An empty tree has height 0 and is balanced. This also ends the recursion past a leaf. - Left height: call
self.height(node.left)and store it inleftHeight. - Pass up a failure: if
leftHeight == -1, return-1immediately. - Right height: do the same with
node.right, storing it inrightHeight. - Pass up a failure from the right the same way. This check matters:
-1would otherwise pass for a height. - Check this node: if
abs(leftHeight - rightHeight) > 1, return-1. Every node runs this on its way back up, so the rule is checked at every node. - Return the height: 1 for the node itself plus
max(leftHeight, rightHeight).
The solution in Python
class Solution:
def height(self, node):
if not node:
return 0
leftHeight = self.height(node.left)
if leftHeight == -1:
return -1
rightHeight = self.height(node.right)
if rightHeight == -1:
return -1
if abs(leftHeight - rightHeight) > 1:
return -1
return 1 + max(leftHeight, rightHeight)
def isBalanced(self, root: Optional[TreeNode]) -> bool:
return self.height(root) != -1
Python details worth knowing:
not node. ATreeNodeobject is truthy andNoneis falsy, soif not nodeis the usual way to writenode is None. It works here because the class doesn't define its own truth value.- Methods call each other through
self. The recursive calls areself.height(...), not bareheight(...). A bare name would raise aNameError. - Returning a comparison.
self.height(root) != -1is already abool, so it is returned directly with noif. - Recursion depth. Python allows about 1000 nested calls by default. The constraints keep the tree at most 800 levels deep, so the recursion fits; a chain of 800 nodes works. A chain of 2000 nodes ends with a
RecursionError. absandmaxare built in.absdrops the sign, so it doesn't matter which side is taller.
Complexity
Time: O(n). Each node is visited once, and the work at a node is a few comparisons. The early returns can only make it faster.
Space: O(h), where h is the height of the tree, for the stack of recursive calls. That is about log n for a well-balanced tree and up to n for a chain. No other memory grows with the input.
Edge cases and common mistakes
- The empty tree.
root = Nonegives height 0, so the result isTrue. - A single node.
[1]has height 1 and is balanced. - Checking only the root. The third example has equal heights at the root and is still unbalanced. The check must run at every node.
- Skipping the right-hand
-1check. Without it, a failure from the right subtree is used as if it were a height. Take the root 1 whose only child, on the right, is a 2 with a left child 3 that has a left child 4. That right subtree is unbalanced, but the root sees a left height of 0 and a right height of -1, a difference of 1, and wrongly accepts it. The correct answer isFalse. - Comparing leaf counts or node counts instead of heights. The rule is about the longest path.
- Counting height in edges. The lesson counts nodes, with 0 for an empty tree. Only the difference matters for the rule, but the base case must match the counting.
Testing
[3, 9, 20, None, None, 15, 7]givesTrue.[1, 2, 2, 3, 3, None, None, 4, 4]givesFalse.[1, 2, 2, 3, None, None, 3, 4, None, None, 4]givesFalse.[]givesTrue.[1]givesTrue.[1, 2, 3]givesTrue.[1, 2, None, 3]givesFalse.
