Validate Binary Search Tree | Leetcode 98

Welcome to our deep dive on Validate Binary Search Tree (Leetcode 98). This problem teaches you that checking just the immediate children of a node is actually not mathematically enough to prove a tree is a valid BST!

Problem Statement

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example: root = [2,1,3] => Output: true

Approach: Recursive Boundary Constraints O(N)

A common trap is to simply verify root.left.val < root.val and root.right.val > root.val. This fails horribly! The entire left subtree (down to the deepest leaf) must strictly be smaller than the root value.

To correctly enforce this, we must pass down acceptable boundaries (a minimum and maximum limit) to every recursive call.

1. Start at the root with boundaries (-infinity, +infinity).
2. When we move to the left child, the node MUST be strictly smaller than its parent. So, we update the maximum boundary to the parent's value! (min_val, parent.val).
3. When we move to the right child, the node MUST be strictly larger than its parent. So, we update the minimum boundary to the parent's value! (parent.val, max_val).
4. If any node breaks its strict allowed boundary, return false.

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        def validate(node, left_boundary, right_boundary):
            if not node:
                return True
                
            # Violates the strict mathematical BST property
            if not (left_boundary < node.val < right_boundary):
                return False
                
            # Validate left (max becomes current) and right (min becomes current)
            return (validate(node.left, left_boundary, node.val) and 
                    validate(node.right, node.val, right_boundary))
            
        return validate(root, float('-inf'), float('inf'))

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (98)