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.

Check with Range

We can check the root's value within a valid range (see https://helloacm.com/teaching-kids-programmaing-recursive-algorithm-to-validate-a-binary-search-tree/:

        def f(root, minv, maxv):
            if not root:
                return True
            if root.val <= minv or root.val >= maxv:
                return False
            return f(root.left, minv, root.val) and f(root.right, root.val, maxv)
        
        return f(root, -inf, inf)

Inorder Traversal

We can perform inorder traversal algorithm and then record the last visited node.

        prev = None
        
        def dfs(root):
            nonlocal prev
            if not root:
                return True
            if not dfs(root.left):
                return False
            if prev and prev.val >= root.val:
                return False
            prev = root
            return dfs(root.right)
            
        return dfs(root)