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 example 1 2 1 3 binary tree 2 1 3 return true example 2 1 2 3 binary tree 1 2 3 return false type root treenode rtype bool type root treenode rtype bool
def is_bst(root):
    

    stack = []
    pre = None
    
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if pre and root.val <= pre.val:
            return False
        pre = root
        root = root.right

    return True