Problem overview
The function isValidBST receives the root of a binary tree (the lesson provides TreeNode, with Val, Left and Right) and returns true when it is a valid binary search tree. For every node, every value in its left subtree must be strictly smaller than the node's value, and every value in its right subtree must be strictly larger. The rule covers whole subtrees, not just the two children.
The tree with root 2, left child 1 and right child 3 is valid. The tree with root 5, a left child 1 and a right child 4 that has children 3 and 6, is not: 4 sits in the right subtree of 5 and is smaller than 5. The tree with root 5, a left child 4 and a right child 6 that has children 3 and 7, is not valid either, and this one is the instructive case. Every node is in order with its own children (4 < 5 < 6 and 3 < 6 < 7), but the 3 lies in the right subtree of 5, where every value must be larger than 5.
Approach: pass a range down the tree
Comparing each node with its children is not enough, because a node must fit every ancestor, not just its parent. The fix is to give each node an allowed range, and to narrow that range as the search goes down:
- The root can hold any value, so its range is unlimited.
- When going into the left child of a node with value
v, everything there must be smaller thanv, so the upper bound becomesv. The lower bound stays what it was. - When going into the right child, the lower bound becomes
vand the upper bound stays.
Each node is checked once against the range it inherited, so the time is O(n).
The bounds are strict: a value equal to a bound breaks the rule, because equal values are not allowed anywhere on either side.
"Unlimited" needs a value that every node value is above and below. Node values can be the smallest and largest 32-bit integers, so those two values can't stand for "no limit": a bound of -2147483648 would reject a node holding exactly -2147483648. Go's int has 64 bits on the machine that runs the lesson's tests, so math.MinInt and math.MaxInt are beyond every 32-bit value and make safe starting bounds.
Step by step
- Start the recursion in
isValidBST. Callvalidateonrootwithmath.MinIntandmath.MaxIntas the bounds, and return its answer. - Write the helper's signature.
validatetakes anodeof type*TreeNodeand two bounds,lowandhigh, and returns abool. It answers whether every value in the tree undernodeis abovelowand belowhigh. Go lets you call a function that is written further down in the file. - Handle the empty tree. If
node == nil, returntrue: an empty tree breaks no rule, and this also ends the recursion past a leaf. - Check this node's value. If
node.Val <= low || node.Val >= high, returnfalse. Both comparisons include equality, because the value must be strictly inside the range. - Check both subtrees with narrowed ranges. The left subtree keeps
lowand getsnode.Valashigh. The right subtree getsnode.Valaslowand keepshigh. Join the two calls with&&.
The solution in Go
func isValidBST(root *TreeNode) bool {
return validate(root, math.MinInt, math.MaxInt)
}
func validate(node *TreeNode, low int, high int) bool {
if node == nil {
return true
}
if node.Val <= low || node.Val >= high {
return false
}
return validate(node.Left, low, node.Val) && validate(node.Right, node.Val, high)
}
Go details worth knowing:
math.MinIntandmath.MaxIntare constants for the smallest and largestint. On a 64-bit build they are -9223372036854775808 and 9223372036854775807. They have existed since Go 1.17.- Nil pointers. A missing child is a
nil*TreeNode, and the base case tests it directly. Because the nil test comes first,node.Valis never read through a nil pointer. - Short-circuit
&&. If the left subtree is invalid, the right one is not visited at all, so the function stops early on a bad tree. - Values are passed by value.
lowandhighare plain ints, so each call has its own range, and narrowing it for the left subtree never affects the right one.
Complexity
Time: O(n), where n is the number of nodes. Each node is visited once and compared against two bounds.
Space: O(h) for the recursion, where h is the height of the tree. The statement allows depth up to 800, which is fine for Go's stack.
Edge cases and common mistakes
- Comparing only with the children. A check that looks only at a node's own left and right child returns
truefor the tree[5, 4, 6, nil, nil, 3, 7], while the range version returnsfalse. - Duplicates. The tree
[2, 2, 2]is invalid, because the children are equal to the root, not strictly smaller or larger. That is why the test uses<=and>=. - Extreme values. A single node holding 2147483647 (the largest 32-bit value) is valid. With bounds of exactly
-2147483648and2147483647, the same single node would be rejected, because the value equals the upper bound. Withmath.MinIntandmath.MaxInt, it passes. - Bounds at the edge of
int. The range bounds are exclusive, so the solution can't accept a node whose value ismath.MinIntitself. That value is far outside the lesson's 32-bit range, and the tree[math.MinInt, nil, 5]returnsfalse. - A single node.
[1]is valid: both subtrees are empty. - Empty tree. A
nilroot returnstrue, since the base case accepts it, though the constraints promise at least one node.
Testing
Trees are written in level order, with nil for a missing child:
[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.[2147483647]givestrue.[-2147483648, nil, 2147483647]givestrue.
