Validate Binary Search Tree: Range bounds Pattern

Learning Outcome

After this lesson, you should be able to explain why checking only parent-child relationships is not enough for validating a BST.

Problem Statement

Given the root of a binary tree, return true if it is a valid binary search tree. Every node in the left subtree must be smaller than the current node, and every node in the right subtree must be larger.

Brute Force Approach

Check every node only against its direct children.

This catches local violations but misses deeper ancestor-bound violations, so it is logically incomplete.

Optimized Approach

Carry a valid range into each recursive call. A node must be strictly greater than the lower bound and strictly less than the upper bound. Left children tighten the upper bound; right children tighten the lower bound.

Exact Pseudocode

valid(node, low, high):
  if node is null:
    return true
  if node.val <= low or node.val >= high:
    return false
  return valid(node.left, low, node.val)
     and valid(node.right, node.val, high)
return valid(root, -infinity, infinity)
  

Reference Code

class Solution:
    def isValidBST(self, root):
        def valid(node, low, high):
            if not node:
                return True
            if node.val <= low or node.val >= high:
                return False
            return valid(node.left, low, node.val) and valid(node.right, node.val, high)

        return valid(root, float("-inf"), float("inf"))
  

Sample Dry Run

Complexity

Edge Cases

• Duplicate values should fail in the strict BST version.
• Very small or very large integer values need wide bounds.
• Ancestor violations deeper in the tree.

Interview Checklist

• Do not check only direct children.
• Carry lower and upper bounds through recursion.
• Use strict inequalities for the common BST definition.

FAQs