Problem overview
The method isBalanced receives the root of a binary tree, a TreeNode | null, and returns true when the tree is height-balanced. A tree is height-balanced when, at every node, the heights of its 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 counts as balanced. The lesson provides the TreeNode class, with the fields val, left and right.
For the tree [3,9,20,null,null,15,7] (level order, null for a missing child), the answer is true: at the root, the left subtree (just 9) has height 1 and the right one (20, 15, 7) has height 2. For [1,2,2,3,3,null,null,4,4] it is false: at the root, the left subtree has height 3 and the right one has height 1.
The rule applies at every node, not only at the root. In [1,2,2,3,null,null,3,4,null,null,4] the root is fine, because both of its subtrees have height 3. But the left 2 has a left subtree of height 2 and an empty right subtree, and 2 and 0 differ by 2, so the answer is false.
Approach: compute heights from the bottom up and check as you go
An obvious method is to write a function height(node), and then at every node compare height(node.left) with height(node.right). It is correct, but each call to height walks a whole subtree, and it is called again for the nodes below. In a tall tree, the same nodes are measured over and over: up to O(n²) time for a chain of n nodes.
The faster idea finds each height only once, from the bottom up, and checks the rule in the same visit. The recursive helper height returns one of two kinds of answer for the tree under a node:
- the real height, when that tree is balanced;
- the signal
-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. Once a subtree reports -1, every node above it passes -1 up at once, without looking at anything else. The tree is balanced exactly when the answer for the root is not -1.
On the first example, the helper visits the leaves first, then their parents, and prints the two heights it found at each node:
node 9 left 0 right 0
node 15 left 0 right 0
node 7 left 0 right 0
node 20 left 1 right 1
node 3 left 1 right 2
Every leaf has two empty subtrees of height 0. Node 20 sees heights 1 and 1, and the root sees 1 and 2. All differences are at most 1, so the result is a real height, 3, and the tree is balanced.
Step by step
- Write
isBalancedin terms of the helper: return whetherthis.height(root)is not -1, using!== -1. - Declare the helper
heightabove it, with one parameternodeof typeTreeNode | null, returning anumber. - Base case: if
nodeisnull, 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.left, and store it inleftHeight. - Pass the signal up: if
leftHeightis -1, return -1 right away. If part of the tree is unbalanced, the whole tree is. - Get the right height the same way, in
rightHeight. - Pass the signal up again if
rightHeightis -1. Don't skip this: -1 would otherwise 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 checked everywhere. - Return the height of the tree under
node: 1 for the node itself plus the larger of the two subtree heights.
The solution in TypeScript
class Solution {
height(node: TreeNode | null): number {
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: TreeNode | null): boolean {
return this.height(root) !== -1;
}
}
Details that matter in TypeScript:
- Methods call each other through
this. Inside a class,heightis not a standalone function, so the recursive call isthis.height(node.left). !nodeas a null check.nullis falsy, and so isundefined, while an object such as aTreeNodeis truthy, so!nodeis true exactly for a missing node. Here aTreeNodeis always an object, even when itsvalis 0.===and!==compare without converting types. The helper's return value is always a number, so they behave as expected.- Union types.
TreeNode | nullsays that the parameter may be a node ornull. This is a compile-time note only: it disappears when the code is compiled to JavaScript. - Recursion depth. The lesson's trees are at most 800 levels deep, which is far below what Node can handle. In a chain of 800 nodes the method returns without a stack problem.
Complexity
Time: O(n). Each node is visited once by height, and each visit does constant work: two recursive calls (or fewer, when -1 comes back early), one subtraction and one comparison.
Space: O(h), where h is the height of the tree. The only extra memory is the call stack, which holds one frame per level of the recursion. In a tree of 800 levels, that is 800 frames at most.
Edge cases and common mistakes
- An empty tree.
root = nullgivesheight(null) = 0, which is not -1, so the answer istrue. - A single node. Both subtrees have height 0, so the answer is
true. - Two nodes.
[1,2]givestrue: heights 1 and 0 differ by 1.[1,2,null,3]givesfalse: heights 2 and 0 differ by 2. - Checking only the root. The third example shows why this fails. The root's subtrees both have height 3, yet the tree is not balanced.
- Forgetting the right-side -1 check. A -1 from the right subtree would then be treated as a height. The difference from an empty left side's 0 would be only 1, and an unbalanced tree could pass.
- Counting edges instead of nodes. The lesson defines height as the number of nodes on the path, so a leaf has height 1 and an empty tree 0. The differences between two subtrees are the same either way, but the base case must return 0.
- Measuring heights again at every node. It gives the right answer but repeats work, which is the O(n²) approach.
Testing
With a small function that builds a tree from a level-order array, the method returned:
[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,null,3]givesfalse.
