Problem overview
The method isValidBST(_ root: TreeNode?) -> Bool returns true when a binary tree 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 strictly larger. The rule covers the whole subtree, not just the two children. The lesson provides the TreeNode class, with val, left and right.
The tree [2, 1, 3] is valid. The tree [5, 1, 4, nil, nil, 3, 6] is not, because the right child of 5 is 4, which is smaller. The tree [5, 4, 6, nil, nil, 3, 7] is not either, and it is the instructive case: 4 < 5 < 6 and 3 < 6 < 7 hold, so every node is in order with its own children, yet 3 sits in the right subtree of 5, where every value must exceed 5.
Approach: each node lives in a range
Comparing each node only with its children misses the third example. The 3 has to satisfy a condition set by an ancestor, the 5, that is two levels up. So instead of looking up, pass the constraint down: each call receives a range (low, high) and requires the node's value to be strictly between them.
The root can be anything, so its range is as wide as possible. Moving to the left child of a node with value v keeps low and lowers high to v: everything on the left must be smaller than v and still respect the bounds from higher up. Moving right keeps high and raises low to v. In the third example, 3 is reached with the range from 5 to 6, since it lies right of 5 and left of 6. It's not greater than 5, so the check fails.
Each node is visited once, so the time is O(n).
Step by step
- Start the check from
isValidBST: callvalidate(root, Int.min, Int.max)and return its answer. The root has no ancestors, so nothing limits it yet. - Declare the helper
validate(_ node: TreeNode?, _ low: Int, _ high: Int) -> Bool. It answers whether every value in the subtree undernodeis larger thanlowand smaller thanhigh. - Accept an empty subtree:
guard let node = node else { return true }. An empty tree breaks no rule, and this also ends the recursion after a leaf. - Reject a value outside the range: if
node.val <= low || node.val >= high, returnfalse. The comparison is strict because equal values are not allowed. - Check both subtrees with their own ranges: the left one gets
(low, node.val), the right one(node.val, high), joined with&&.
The solution in Swift
class Solution {
func validate(_ node: TreeNode?, _ low: Int, _ high: Int) -> Bool {
guard let node = node else {
return true
}
if node.val <= low || node.val >= high {
return false
}
return validate(node.left, low, node.val) && validate(node.right, node.val, high)
}
func isValidBST(_ root: TreeNode?) -> Bool {
return validate(root, Int.min, Int.max)
}
}
The Swift details worth a closer look:
- Why
Int.minandInt.maxwork as "no limit". A node value is between -2^31 and 2^31 - 1, butIntin Swift is 64 bits, andInt.minis -9223372036854775808 andInt.maxis 9223372036854775807. Both lie beyond every value a node can hold, so the strict comparison never rejects a legitimate root. The tree[2147483647]and the tree[-2147483648]are both valid, and the bounds don't interfere. In a language with 32-bit integers, using the extreme values as bounds would wrongly reject such nodes. guard let node = nodereplaces the optional with a non-optional constant of the same name. Theelsebranch must leave the function, here withreturn true.- The
_labels. Parameters declared with_are called without labels:validate(root, Int.min, Int.max). - Short-circuit
&&. If the left subtree is invalid, the right call is not made.
Complexity
Time: O(n). Each node is visited once, with constant work.
Space: O(h) for the recursion, where h is the height of the tree. The tree is at most 800 levels deep, which the call stack handles.
Edge cases and common mistakes
- Comparing only with children. This accepts
[5, 4, 6, nil, nil, 3, 7], which is invalid. - Using
<instead of<=in the rejection test. Equal values would pass.[2, 2, 2]and[1, 1]must be rejected, and the lesson's code does that. - A single node.
[1]is valid, and so is a tree holding the extreme 32-bit values, such as[-2147483648, nil, 2147483647]. - Swapping the bounds. The left subtree is capped by
node.valfrom above, the right one is floored by it from below. Mixing them up rejects every valid tree with a left child, even[2, 1, 3]. - Bounds smaller than the data. If a bound could equal a legitimate value, the strict check would reject it. In Swift, a 64-bit
Intleaves room.
Testing
[2, 1, 3]givestrue.[5, 1, 4, nil, nil, 3, 6]givesfalse.[5, 4, 6, nil, nil, 3, 7]givesfalse.[1]givestrue.[2, 2, 2]givesfalse.[1, 1]givesfalse.[2147483647]givestrue.[-2147483648, nil, 2147483647]givestrue.[3, 1, 5, 0, 2, 4, 6]givestrue.
