Validate Binary Search Tree
MediumThe problem
A valid binary search tree has this rule at every node: all values in its left subtree are smaller than it, and all values in its right subtree are bigger. Return true if the tree follows the rule everywhere, otherwise false.
- Example 1Input: root = [2, 1, 3]Output: true
- Example 2Input: root = [5, 1, 4, null, null, 3, 6]Output: false
The node 4 is on the right of 5 but is smaller than 5.
- Example 3Input: root = [5, 4, 6, null, null, 3, 7]Output: false
3 is below 6 which is fine, but 3 is also in the right subtree of 5 and is smaller than 5.
- 1 ≤ number of nodes ≤ 10,000
- -2^31 ≤ node value ≤ 2^31 - 1
- Equal values are not allowed on either side
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Checking only parent vs child is not enough — every node in the left subtree must be smaller than the root.
The idea
DFS with an allowed range (low, high); going left tightens high to node.val, going right tightens low. (Or inorder must be strictly increasing.)
Target: O(n) time
Go function shape
func isValidBST(root *TreeNode) boolReference solution
Tested with go test. Try it yourself first, then compare.
// IsValidBST: pass the allowed (lo, hi) range down, not just the parent.
// nil bounds mean "unbounded", which also handles Val == MinInt/MaxInt safely.
func IsValidBST(root *TreeNode) bool {
var check func(n *TreeNode, lo, hi *int) bool
check = func(n *TreeNode, lo, hi *int) bool {
if n == nil {
return true
}
if (lo != nil && n.Val <= *lo) || (hi != nil && n.Val >= *hi) {
return false
}
return check(n.Left, lo, &n.Val) && check(n.Right, &n.Val, hi)
}
return check(root, nil, nil)
}