98. Validate Binary Search Tree

Validate Binary Search Tree - LeetCode

left < node < right is a valid binary search tree Input: [2,1,3] Output: true 2 /
1 3


  • code
class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, null, null);
    }
    
    private boolean check(TreeNode node, Integer low, Integer high){
        if (node == null) return true;
        if ((low != null && node.val <= low) || (high != null && node.val >= high)) return false;
        return check(node.left, low, node.val) && check(node.right, node.val, high);
    }
}
  • code
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        res_inorder = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res_inorder.append(root.val)
            inorder(root.right)

        inorder(root)
        for i in range(len(res_inorder)-1):
            if res_inorder[i] >= res_inorder[i+1]:
                return False
        return True



  • code
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:

        def validate(node, low=-math.inf, high=math.inf):
            # Empty trees are valid BSTs.
            if not node:
                return True
            # The current node's value must be between low and high.
            if node.val <= low or node.val >= high:
                return False

            # The left and right subtree must also be valid.
            return (validate(node.right, node.val, high) and
                   validate(node.left, low, node.val))

        return validate(root)