Validate Binary Search Tree

[huimeich]

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a 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.

[huimeich]

def isValidBST(self, root: TreeNode) -> bool:
    stack = []
    inorder = float("-inf")
    while True:
        while root:
            stack.append(root)
            root = root.left
        if len(stack) > 0:
            root = stack.pop()
            if inorder >= root.val:
                return False
            inorder = root.val
            root = root.right
        else:
            return True

[huimeich]

def isValidBST(self, root: TreeNode) -> bool:
    def helper( root: TreeNode, lv: float, rv: float) -> bool:
        if root == None:
            return True
        val = root.val
        if val <= lv or val >= rv:
            return False
        if not helper(root.left, lv, val):
            return False
        if not helper(root.right, val, rv):
            return False
        return True
    return helper(root, float('-inf'), float('inf'))

[huimeich]

    if not root:
        return True
    stack = []
    stack.append((root, float('-inf'), float('inf')))
    while len(stack) > 0:
        (root, lv, rv) = stack.pop()
        if not root:
            continue
        val = root.val
        if val >= rv or val <= lv:
            return False
        stack.append((root.left, lv, val))
        stack.append((root.right, val, rv))
    return True