Validate Binary Search Tree

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.

Conditions

Think about what makes a binary search tree valid; all left nodes must be smaller than their parent node, while all right nodes must be larger than their parent nodes. This has to happen infinitely, so we need to find a way to keep track of the previous parent.

Start off with the current node. If it is None, we know we’ve validated properly. return True.

If the node’s val is outside the bounds of the right parent and left parent, we have an incorrect node. return False.

Otherwise, check the children.

When checking the left child, make sure that the left val comes from the grandparent, since the child’s value has to be less than the parent’s expectation. As well, the right child’s value has to be greater than the right.

def check(node, left, right):
    if node is None:
        return True
    if not left < node.val < right:
        return False
    return check(node.left, left, node.val) and check(node.right, node.val, right)

return check(root, float('-inf'), float('inf'))