38. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST has: left subtree nodes strictly less than the node, right subtree nodes strictly greater than the node, and both subtrees must also be valid BSTs.

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

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.

Problem Breakdown:

1. Use recursive validation with min/max bounds. Each node must fall within a valid range. The root has no bounds (negative infinity to positive infinity).

• def isValidBST(root):
      return validate(root, float('-inf'), float('inf'))

2. For each node, check if its value is within the allowed range (low, high). If not, the tree is invalid.

• def validate(node, low, high):
      if not node:
          return True
      if node.val <= low or node.val >= high:
          return False

3. Recursively validate the left subtree with an updated upper bound (current node's value) and the right subtree with an updated lower bound.

•     return validate(node.left, low, node.val) and validate(node.right, node.val, high)

Summary:

Pass valid value ranges down the recursion. Each left child must be less than its parent (update upper bound), and each right child must be greater (update lower bound). A node outside its range invalidates the BST.

Time and Space Complexity:

Time Complexity: O(n) - we visit each node once.

Space Complexity: O(h) - recursion stack depth equals the tree height.

Python Solution:

def isValidBST(root):
    def validate(node, low, high):
        if not node:
            return True
        if node.val <= low or node.val >= high:
            return False
        return validate(node.left, low, node.val) and validate(node.right, node.val, high)
    return validate(root, float('-inf'), float('inf'))

JavaScript Solution:

var isValidBST = function(root) {
    const validate = (node, low, high) => {
        if (!node) return true;
        if (node.val <= low || node.val >= high) return false;
        return validate(node.left, low, node.val) && validate(node.right, node.val, high);
    };
    return validate(root, -Infinity, Infinity);
};

Java Solution:

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean validate(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return validate(node.left, low, node.val) && validate(node.right, node.val, high);
    }
}