Problem overview
The method isValidBST receives the root of a binary tree and returns true if it is a valid binary search tree. For every node, all values in its left subtree must be strictly smaller than the node's value, and all values in its right subtree must be strictly larger. The rule covers whole subtrees, not just the two children. The lesson provides the TreeNode class, with an int val, a TreeNode left, a TreeNode right and a constructor TreeNode(int x).
The tree [2, 1, 3] is valid. The tree [5, 1, 4, null, null, 3, 6] is not, because the right child of 5 is 4, which is smaller. The tree [5, 4, 6, null, null, 3, 7] is not valid either, and it is the instructive one: every node is in order with its own children (4 < 5 < 6 and 3 < 6 < 7), but 3 sits in the right subtree of 5, where every value must be larger than 5.
Approach: pass a range down the tree
The natural first idea is to compare each node with its two children. That check accepts [5, 4, 6, null, null, 3, 7], because it never compares 3 with 5. In the lesson's runs, such a children-only check returned true for that tree and also for [10, 5, 15, null, null, 6, 20], where 6 lies in the right subtree of 10. Both trees are invalid.
The fix is to give each node the range that all of its ancestors allow. The root can hold any value, so it starts with no limit. Going into the left child, the node's own value becomes the new upper limit, because everything on the left must be smaller. Going into the right child, the node's value becomes the new lower limit. A node is valid when its value lies strictly between the two limits and both of its subtrees are valid with their narrowed ranges. Each node is visited once, so the time is O(n).
The limits need a "no limit yet" value, and here that is the tricky part. Node values can be the smallest or the largest int. A limit stored as Integer.MIN_VALUE would reject a legitimate node holding exactly that value, since the comparison is strict. The solution therefore keeps its limits in long variables, starting at Long.MIN_VALUE and Long.MAX_VALUE, which are beyond every int.
Step by step
isValidBST
- Call the helper
validateonrootwith the widest range,Long.MIN_VALUEandLong.MAX_VALUE, and return its answer. Nothing above the root limits it.
validate
- Declare it to return
boolean, taking aTreeNode nodeand twolongbounds,lowandhigh. It answers whether every value in the tree undernodeis larger thanlowand smaller thanhigh. - Return
trueifnodeisnull. An empty tree breaks no rule, and this stops the recursion past a leaf. - Return
falseifnode.val <= low || node.val >= high. The comparison is strict, so a value equal to a bound is also invalid. Java widens theintto alongfor the comparison. - Check both subtrees with
&&. The left one keepslowand getsnode.valas its upper bound. The right one getsnode.valas its lower bound and keepshigh.
The solution in Java
class Solution {
boolean validate(TreeNode node, long low, long high) {
if (node == null) {
return true;
}
if (node.val <= low || node.val >= high) {
return false;
}
return validate(node.left, low, node.val) && validate(node.right, node.val, high);
}
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}
Java details worth noticing:
- Widening conversions.
node.valis anint, and passing it where alongis expected is allowed without a cast. The same happens in the comparisonsnode.val <= low. - Why
longbounds. Withintbounds starting atInteger.MIN_VALUEandInteger.MAX_VALUE, the single-node trees[-2147483648]and[2147483647]were both wrongly rejected, and so was[0, -2147483648, 2147483647]. With thelongbounds all three are accepted, which is correct. - Short-circuit
&&. If the left subtree is invalid, the right one is not examined at all. - Recursion depth. The tree is at most 800 levels deep, which the default Java stack handles. A right-leaning chain of 800 nodes with increasing values returns
true.
Complexity
Time: O(n). Each node is visited once, and each visit does a constant amount of work. Visiting stops early at the first invalid node.
Space: O(h), where h is the height of the tree, for the recursion stack. It is at most 800 here, and O(log n) for a balanced tree.
Edge cases and common mistakes
- Comparing only with children. It passes
[5, 4, 6, null, null, 3, 7]and[10, 5, 15, null, null, 6, 20], which are invalid. - Duplicates. Equal values are not allowed on either side.
[2, 2, 2]and[1, 1]both givefalse. Using<and>in the rejection test instead of<=and>=would accept them. - Extreme values.
[-2147483648, null, 2147483647]is valid. This is the reason forlongbounds. - A single node.
[1]is valid whatever its value, because both bounds are far outside theintrange. - Passing the wrong bound. The left subtree narrows
high, and the right subtree narrowslow. Swapping them rejects valid trees such as[2, 1, 3]. - Narrowing both bounds at once. Each child changes only one limit and inherits the other from higher up. That inheritance is what lets a deep node feel the influence of the root.
- Skewed trees.
[3, null, 4, null, 5]is valid: a chain is fine as long as the values keep increasing to the right.
Testing
[2, 1, 3]givestrue.[5, 1, 4, null, null, 3, 6]givesfalse.[5, 4, 6, null, null, 3, 7]givesfalse.[2, 2, 2]givesfalse.[-2147483648]givestrue.[0, -2147483648, 2147483647]givestrue.[10, 5, 15, null, null, 6, 20]givesfalse.[5, 3, 7, 2, 4, 6, 8]givestrue.
