Problem overview
Given the root of a binary tree, isBalanced 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, and an empty tree has height 0 and counts as balanced. The lesson provides the TreeNode class (a node with a value, and left and right children that can be null), so you don't define it.
For the tree [3, 9, 20, null, null, 15, 7], the root's left subtree (just the 9) has height 1 and its right subtree (20 with 15 and 7) has height 2. They differ by 1, and the node 20 has two subtrees of height 1, so the tree is balanced. For [1, 2, 2, 3, 3, null, null, 4, 4] the root's left subtree has height 3 and its right subtree height 1, a difference of 2, so the answer is false.
Approach
The first idea is to write a function that measures the height of a tree, and then, for every node, compare the heights of its two subtrees. That works, but each node's height is measured again for every node above it, which repeats work: on a tree shaped like a long chain this adds up to O(n²).
The lesson measures every 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 it passes the signal up at once.
Step by step
- The entry point.
isBalancedreturnsheight(root) != -1. - The helper's signature.
heighttakes anodeof typeTreeNode?and returns anInt. It returns the number of levels undernodewhen that tree is balanced, and-1when it isn't. - The base case. If
node == null, return 0: an empty tree is balanced and has height 0. This also stops the recursion after a leaf. - The left side. Store
height(node.left)inval leftHeight. Trust the recursion: it gives the left subtree's height, or -1. - Pass up a left failure. If
leftHeight == -1, return -1 right away, without even looking at the right subtree. - The right side. Do the same with
node.rightandval rightHeight. A missing child gives 0, thanks to the base case. - Pass up a right failure. If
rightHeight == -1, return -1. Don't skip this check: -1 would otherwise pass for a height and differ from an empty side's 0 by only 1. - The rule at this node. If
Math.abs(leftHeight - rightHeight) > 1, return -1. Every node runs this on its way back up, so the rule is checked at every node and not only at the root. - The height. Return
1 + maxOf(leftHeight, rightHeight): this node plus the taller subtree.
The solution in Kotlin
class Solution {
fun height(node: TreeNode?): Int {
if (node == null) {
return 0
}
val leftHeight = height(node.left)
if (leftHeight == -1) {
return -1
}
val rightHeight = height(node.right)
if (rightHeight == -1) {
return -1
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1
}
return 1 + maxOf(leftHeight, rightHeight)
}
fun isBalanced(root: TreeNode?): Boolean {
return height(root) != -1
}
}
Kotlin details:
TreeNode?means the node may benull. After theif (node == null) return 0check, Kotlin smart-castsnodeto a non-nullTreeNode, sonode.leftneeds no?.or!!. The children areTreeNode?again, which fits the parameter type.Math.absis Java's, available on the JVM.kotlin.math.abswould do the same job, but would need an import.maxOf(a, b)is a Kotlin standard-library function that returns the larger of two values.isBalancedusesheight, which sits above it in the class. In a Kotlin class the order of members does not matter.- The recursion depth equals the height of the tree. The statement promises at most 800 levels, which the JVM handles without trouble.
A trace
For [3, 9, 20, null, null, 15, 7], printing the two subtree heights at each node as it finishes shows the bottom-up order:
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
Each pair differs by at most 1, so every node returns a real height, and the root returns 3. For [1, 2, 2, 3, null, null, 3, 4, null, null, 4], the root's two subtrees have the same height, so a check at the root alone passes. But at the left 2 the subtrees have heights 2 and 0, a difference of 2, so height returns -1 there, the signal travels up, and isBalanced returns false. Calling height on that tree directly returns -1.
Complexity
Time: O(n), where n is the number of nodes. Each node is visited once and does a constant amount of work. In the failing case the search stops early.
Space: O(h) for the recursion, where h is the height of the tree. That is O(log n) for a well-balanced tree and up to O(n) for a chain.
Edge cases and common mistakes
- Checking only the root. The rule holds at every node. The third example has equal heights at the root but fails lower down.
- Forgetting the
-1checks. If you skip the checks onleftHeightandrightHeight, a failure's-1is treated as a height and the signal gets lost. - An empty tree (
root == null) is balanced:heightreturns 0, which is not -1, so the result istrue. - A single node is balanced, and so is a root with one child (heights 1 and 0).
- A chain of three. A root with a left child that has its own left child has subtree heights 2 and 0 at the root, so it is not balanced.
Testing
Trees are written in level order. These were run against the solution above:
| Tree | Result |
|---|---|
[3, 9, 20, null, null, 15, 7] | true |
[1, 2, 2, 3, 3, null, null, 4, 4] | false |
[1, 2, 2, 3, null, null, 3, 4, null, null, 4] | false |
[] (empty) | true |
[1] | true |
[1, 2] | true |
[1, 2, null, 3] | false |
