Problem overview
The method isBalanced(root) 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 node type: a TreeNode with val, left and right, where a missing child is null.
Written in level order, [3, 9, 20, null, null, 15, 7] is balanced: at the root the subtrees have heights 1 and 2, and at 20 both 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 height 1. The tree [1, 2, 2, 3, null, null, 3, 4, null, null, 4] is not either, although the root's two subtrees are equally tall: the left 2 has a left subtree of height 2 and an empty right subtree, so the rule fails at that node. The rule has to hold at every node, not only at the root.
The statement asks for O(n) time, visiting each node once.
Approach: compute heights from the bottom up and check on the way
The obvious solution writes a height function and, at every node, compares height(node.left) with height(node.right), recursing into both children. It is correct, but each call to height walks a whole subtree again, so the nodes near the top are measured many times. On a long, thin tree this approaches O(n²).
The faster way does both jobs in one trip. A recursive height returns the height of the tree under a node, but it also checks the rule at that node while the heights are at hand. When a node breaks the rule, height returns the signal -1. A real height is never negative, so -1 can't be confused with one. Every caller passes the signal up, and isBalanced only asks whether the final answer is -1.
For the example trees, the root's height results are:
[3,9,20,null,null,15,7] isBalanced: true height() = 3
[1,2,2,3,3,null,null,4,4] isBalanced: false height() = -1
[1,2,2,3,null,null,3,4,null,null,4] isBalanced: false height() = -1
[] isBalanced: true height() = 0
[1,2,null,3] isBalanced: false height() = -1
In the third tree, the left child 2 is where the rule fails. It returns -1, and the root passes that along without looking at its right side.
Step by step
- Make
isBalanceda thin wrapper. It returnsthis.height(root) !== -1. The strict comparison!==is true when the two sides differ, and no type conversion is involved. - Declare the helper
height(node). It returns the number of levels undernodeif that tree is balanced, and-1if it isn't. - Base case. If
nodeisnull(!node), return 0. An empty tree is balanced with height 0, and this check also ends the recursion past the leaves. - Get the left height with a recursive call on
node.left, in aletnamedleftHeight. - Pass the signal up. If
leftHeightis-1, return-1at once. The whole tree is unbalanced, so the right side doesn't need to be examined. - Get the right height the same way into
rightHeight. A missing child yields 0 thanks to the base case. - Pass the signal up again. This check is not optional: without it,
-1would be treated as a height, and it differs from an empty side's 0 by only 1, so the rule could pass by mistake. - Check this node. If
Math.abs(leftHeight - rightHeight) > 1, return-1. Every node runs this on the way back up, so the rule is applied everywhere.Math.absdrops the sign, so it doesn't matter which side is taller. - Return the height: 1 for this node plus the larger of the two subtree heights, with
Math.max.
The solution in JavaScript
class Solution {
height(node) {
if (!node) {
return 0;
}
let leftHeight = this.height(node.left);
if (leftHeight === -1) {
return -1;
}
let rightHeight = this.height(node.right);
if (rightHeight === -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return 1 + Math.max(leftHeight, rightHeight);
}
isBalanced(root) {
return this.height(root) !== -1;
}
}
JavaScript details worth knowing:
!nodeas a null check. The lesson's nodes usenullfor a missing child, and!nullistrue. The same test is also true forundefinedand for0, but a node is an object, which is always truthy, so here it only catches the missing-child case.this.heightinside a class. Methods of a class don't see each other as plain names. To callheightfrom another method, writethis.height(...). When the recursion calls itself it usesthis.heighttoo.- Method order doesn't matter.
isBalancedcomes afterheightin the file, but the order in a class body has no effect on which methods can call which. - Recursion depth. The tree can be up to 800 levels deep. Recursion that deep is well within what Node's call stack allows.
Complexity
Time: O(n). Each node is visited once, and the work at a node is a constant number of comparisons. When a node returns -1, the calls above it return right away, so a failing tree is never visited more than once either.
Space: O(h) for the call stack, where h is the height of the tree. It is about log n for a balanced tree and up to n for a chain. No other memory is used.
Edge cases and common mistakes
- Empty tree.
[]is balanced.rootisnull,heightreturns 0, and 0 is not-1. - Single node.
[1]has height 1 and is balanced.[1, 2]is balanced too: the heights are 1 and 0, which differ by 1. - A chain of two below the root.
[1, 2, null, 3]is unbalanced: the root's left side has height 2 and its right side height 0. - Checking only the root. The third example tree has equal subtree heights at the root and is still unbalanced. The rule applies at every node.
- Forgetting to check
rightHeightfor-1. The signal would then be used as a height, and an unbalanced right subtree could slip through as balanced. - Using a separate height function at each node. It gives the right answer and then repeats work, as explained above.
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.[]givestrue.[1]givestrue.[1, 2]givestrue.[1, 2, 3]givestrue.[1, 2, null, 3]givesfalse.- A chain of 800 nodes, each the left child of the one above, gives
false.
