Validate Binary Search Tree

Problem

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 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
-2^31 <= Node.val <= 2^31 - 1

Solution

Approach: DFS with Range Validation

The key insight is to track valid range for each node. Root can be any value, left children must be less, right children must be greater.

Implementation

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def validate(node, min_val, max_val):
            if not node:
                return True

            # Check if current node violates BST property
            if not (min_val < node.val < max_val):
                return False

            # Recursively validate subtrees with updated ranges
            return (validate(node.left, min_val, node.val) and
                    validate(node.right, node.val, max_val))

        return validate(root, float('-inf'), float('inf'))

Alternative (Inorder Traversal):

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.prev = float('-inf')

        def inorder(node):
            if not node:
                return True

            # Check left subtree
            if not inorder(node.left):
                return False

            # Check current node
            if node.val <= self.prev:
                return False
            self.prev = node.val

            # Check right subtree
            return inorder(node.right)

        return inorder(root)

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(h), where h is the height of the tree (recursion stack).

Key Insights

Range Constraint: Each node must be within a valid range determined by its ancestors, not just compared to its parent.
Subtree Constraint: All nodes in left subtree must be less than root, not just the immediate left child.
Inorder Property: In a valid BST, inorder traversal produces a strictly increasing sequence.
Strict Inequality: Values must be strictly less/greater, not less/greater or equal.
Recursive Range Updates: For left child, max becomes parent’s value. For right child, min becomes parent’s value.