Skip to content

98. Validate Binary Search Tree

Problem Link

For a valid BST, each node must satisfy constraints imposed by all of its ancestors, not just its immediate parent. Simply comparing a node with its left and right children is not sufficient.

This can be done by using a DFS traversal with two additional parameters lower_bound and upper_bound, which are used to check validity of each node:

  • lower_bound: the minimum value the node is allowed to take
  • upper_bound: the maximum value the node is allowed to take

At each node:

  • If the node is None, it is trivially valid.
  • Otherwise, the node’s value must lie within the current bounds.
  • When moving to the left subtree, the upper bound becomes node.val - 1, since all values must be strictly smaller.
  • When moving to the right subtree, the lower bound becomes node.val + 1, since all values must be strictly larger.
Pseudocode 
function validate(node, upper, lower):
if node is null:
return true
if node.val < lower OR node.val > upper:
    return false

return validate(node.left, node.val - 1, lower)
       AND validate(node.right, upper, node.val + 1)
Runtime Complexity

Time: \(O(n)\), where \(n\) is the number of nodes in the tree

Space: \(O(h)\), where \(h\) is the height of the tree due to recursion stack

class Solution:
    def _helper(self, node, upper_bound, lower_bound):
        if not node:
            return True

        return lower_bound <= node.val <= upper_bound and \
            self._helper(node.left, node.val-1, lower_bound) and \
            self._helper(node.right, upper_bound, node.val+1)

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        return self._helper(root, float('inf'), float('-inf'))

func isValidBST(root *TreeNode) bool {
    var helper func(node *TreeNode, upperLimit, lowerLimit int) bool
    helper = func(node *TreeNode, upperLimit, lowerLimit int) bool {
        if node == nil {
            return true
        }
        return lowerLimit <= node.Val && node.Val <= upperLimit && helper(node.Left, node.Val-1, lowerLimit) &&
            helper(node.Right, upperLimit, node.Val+1)
    }
    return helper(root, math.MaxInt, math.MinInt)
}