Medium

Validate Binary Search Tree

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.

Examples

Input:root = [2,1,3]

Output:true

Input:root = [5,1,4,null,null,3,6]

Output:false

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

Approach

A node in a BST must satisfy constraints imposed by its ancestors. The root can have any value (between negative and positive infinity). When traversing left, the maximum allowed value becomes the parent's value. When traversing right, the minimum allowed value becomes the parent's value. We use a recursive function passing these lower and upper boundaries.

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)

This approach optimally checks constraints at every node.

Solution.java

1class Solution {2    public boolean isValidBST(TreeNode root) {3        return valid(root, null, null);4    }5    6    // Use Integer class to allow null boundaries7    private boolean valid(TreeNode node, Integer low, Integer high) {8        if (node == null) return true;9        10        if (low != null && node.val <= low) {11            return false;12        }13        if (high != null && node.val >= high) {14            return false;15        }16        17        return valid(node.left, low, node.val) && valid(node.right, node.val, high);18    }19}