98. Validate Binary Search Tree

Description

The task is to determine whether a given binary tree is a valid Binary Search Tree (BST). A BST is defined such that for each node, the left subtree only contains nodes with values less than the node's value, and the right subtree only contains nodes with values greater than the node's value.

Intuition

The key to solving this problem is to perform a depth-first traversal (in-order traversal) of the tree while validating each node against upper and lower bounds to ensure it satisfies the BST properties.

Approach

1. Recursive Approach: - Implement a recursive function that checks each node, passing down the valid range (min and max) that the node's value must fit within. - At each node, check if its value is within the current valid range. - Recursively check the left and right subtrees, updating the valid range accordingly.
2. Base Case: - If a node is None, it is considered a valid BST subtree.
3. Edge Cases: - Handle cases where the tree is empty (root is None).

Complexity

Time Complexity:

O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once.

Space Complexity:

O(h), where h is the height of the tree. This is due to the recursive stack space used by the function.

Code

C++

class Solution {
public:
    bool isValidBST(TreeNode* root, TreeNode* minNode = nullptr, TreeNode* maxNode = nullptr) {
        if (!root) return true;

        if (minNode && root->val <= minNode->val) {
            return false;
        }
        if (maxNode && root->val >= maxNode->val) {
            return false;
        }

        return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
    }
};

Python

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def is_valid(node, min_val, max_val):
            if not node:
                return True
            
            if (min_val is not None and node.val <= min_val) or (max_val is not None and node.val >= max_val):
                return False
            
            return is_valid(node.left, min_val, node.val) and is_valid(node.right, node.val, max_val)
        
        return is_valid(root, float('-inf'), float('inf'))

Java

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }
        
        if (min != null && node.val <= min) {
            return false;
        }
        if (max != null && node.val >= max) {
            return false;
        }
        
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }
}

JavaScript

var isValidBST = function (root, min = null, max = null) {
    if (root == undefined) return true


    if (min !== null && root.val <= min) {
        return false
    }
    if (max !== null && root.val >= max) {
        return false
    }
    
    var rLeft = isValidBST(root.left, min, root.val)
    var rRight = isValidBST(root.right, root.val, max)

    return rLeft && rRight
}