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 lesson provides the TreeNode class, whose nodes have the fields val, left and right. A missing child is null.
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. For the tree [3, 9, 20, null, null, 15, 7] the root's left subtree (the node 9) has height 1 and its right subtree (20 with 15 and 7) has height 2. They differ by 1, and the other nodes are fine too, so the answer is true. For [1, 2, 2, 3, 3, null, null, 4, 4] the left subtree of the root has height 3 and the right has height 1, so the answer is false.
The rule holds at every node, not just at the root. In [1, 2, 2, 3, null, null, 3, 4, null, null, 4] the root is fine (both sides have height 3), but the left 2 has a subtree of height 2 on one side and nothing on the other. The answer is false.
Approach: compute heights once, from the bottom up
The obvious solution is to write a Height method and call it on both children of every node. That works, but the same subtrees get measured again and again, once for every node above them. For a tree shaped like a long chain, that is O(n^2) time.
The better idea is to combine the two jobs. A recursive Height method returns the height of the tree under a node, and it checks the rule on the way back up. When it finds a node that breaks the rule, it returns -1 instead of a height. A real height is never negative, so -1 can't be mistaken for one: it means "unbalanced somewhere in here". Every caller passes the signal up at once.
The check at one node has four parts: get the left height, stop if it is -1; get the right height, stop if it is -1; compare the two heights, and stop with -1 if they differ by more than 1; otherwise return 1 plus the larger height. Each node is visited once, and each height is found once. For the three examples, Height(root) returns 3, then -1, then -1.
Step by step
- In
IsBalanced, return whetherHeight(root) != -1. This is the whole method; the helper does the work. - Declare
Heightas a public method that returns anintand takes aTreeNodenamednode. - Base case: if
node == null, return 0. An empty tree is balanced and has height 0. This also stops the recursion at the leaves. - Left subtree: call
Height(node.left)and store it inleftHeight. - Pass the signal up: if
leftHeight == -1, return -1 without looking at the right subtree. - Right subtree: store
Height(node.right)inrightHeight. A missing child gives 0 here, thanks to the base case. - Pass the signal up again: if
rightHeight == -1, return -1. Don't skip this check: -1 differs from an empty side's 0 by only 1, so it would otherwise pass for a height. - Check this node: if
Math.Abs(leftHeight - rightHeight) > 1, return -1. Every node runs this code on its way back up, so the rule is checked at every node. - Return the height: 1 for the node itself plus
Math.Max(leftHeight, rightHeight).
The solution in C#
class Solution {
public 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 bool IsBalanced(TreeNode root) {
return Height(root) != -1;
}
}
The C# details worth knowing:
- Reference types can be
null. ATreeNodevariable holds a reference, sonode == nullis how the code tests for a missing child. Readingnode.leftwhennodeisnullwould throw aNullReferenceException, which is why the base case comes first. - A sentinel value. Returning -1 to mean "unbalanced" is a common trick for returning two kinds of information (a height or a failure) in one
int. It only works because real heights are never negative. Math.AbsandMath.Maxare in theSystemnamespace. In a file of your own, addusing System;.- Methods can call each other in any order. In C#, a method inside a class may use a method written below it. The lesson writes
Heightfirst only because the steps build it that way. - Recursion depth. Each recursive call uses stack space. The tests have at most 800 levels, which is far from the limit, but a tree with hundreds of thousands of levels could crash a recursive solution with a stack overflow.
Complexity
Time: O(n). Each node is visited once and does a constant amount of work, and the early returns only make it faster.
Space: O(h), where h is the height of the tree. The recursion goes as deep as the tree does: about log n levels for a balanced tree, and up to n for a chain. The method creates no data structures of its own.
Edge cases and common mistakes
- An empty tree.
IsBalanced(null)returnstrue, sinceHeight(null)is 0. - One node.
[5]has height 1 and is balanced. - Two nodes.
[1, 2]has height 2 and is balanced: the sides have heights 1 and 0. - A chain of three.
[1, 2, null, 3]returnsfalse: at the root the sides have heights 2 and 0. A chain of 800 nodes returnsfalseas well. - Only checking the root. The third example has a root with two sides of equal height, and is still unbalanced. The check must run at every node.
- Treating -1 as a height. If a call skips the
-1checks, a failure turns into a small number, and a node above can end up with a difference of at most 1. The tree then looks balanced. - Counting edges instead of nodes. The lesson counts nodes, so a leaf has height 1 and an empty tree 0. The difference test works either way, but the base case has to match the definition.
- Recomputing heights for every node. It gives the right answer but takes O(n^2) time on a chain.
Testing
[3, 9, 20, null, null, 15, 7]givestrue(height 3).[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. [5]givestrue.[1, 2]givestrue.[1, 2, null, 3]givesfalse.[1, 2, 3, 4]givestrue.
