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.


&nbsp;
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.


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 104].
	-231 &lt;= Node.val &lt;= 231 - 1


# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def valid(node,left,right):
            if not node: # checking node is none
                return True
            if not (node.val>left and node.val<right): # checking the left value is less than node and right value is greater than node
                return False
            return (valid(node.left,left,node.val) and valid(node.right,node.val,right)) # recursively calling left child and right child and returing the result True if both are true else False

        return valid(root,float("-inf"),float("inf")) #calling recursive function to check
class Solution {
    public boolean isValidBST(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    public boolean dfs(TreeNode root, int min, int max) {
        if (root.val < min || root.val > max || (root.val == Integer.MIN_VALUE && root.left != null) ||                    (root.val == Integer.MAX_VALUE && root.right != null)) return false;
        boolean leftRight = true;
        if (root.left == null && root.right == null) return true;
        if (root.left != null) {
            leftRight = dfs(root.left, min, root.val - 1);
        }
        if (root.right != null) {
            leftRight = dfs(root.right, root.val + 1, max) && leftRight;
        }
        return leftRight;
    }
}
// We know inorder traversal of BST is always sorted, so we are just finding inorder traversal and check whether it is in sorted manner or not, but only using const space using prev pointer.
class Solution {
public:
    TreeNode* prev;
    Solution(){
        prev = NULL;
    }
    bool isValidBST(TreeNode* root) {
        if (root == NULL)
            return true;
        bool a = isValidBST(root->left);
        if (!a)
            return false;
        if (prev != NULL)
        {
            if (prev->val >= root->val)
                return false;
        }
        prev = root;
        return isValidBST(root->right);
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    const nodesToCheck = [{node: root, lowerLimit: -Infinity, upperLimit: Infinity}]
    
    while (nodesToCheck.length > 0) {
        const {node: currentNode, lowerLimit, upperLimit} = nodesToCheck.pop()
        
        if (currentNode.val <= lowerLimit || currentNode.val >= upperLimit) {
            return false
        }
        
        if (currentNode.left) {
            nodesToCheck.push({
                node: currentNode.left,
                lowerLimit,
                upperLimit: currentNode.val
            })
        }
        
        if (currentNode.right) {
            nodesToCheck.push({
                node: currentNode.right,
                lowerLimit: currentNode.val,
                upperLimit
            })
        }
    }
    
    return true
};
Validate Binary Search Tree