Validate Binary Search Tree

Intuition

Checking a node only against its immediate children is not enough, because a deep descendant can still violate an ancestor's constraint. Instead, carry an allowed open interval (low, high) into every call that captures the strictest bounds imposed by all ancestors. A node is valid only if its value lies strictly between low and high. When we descend left, the current value becomes the new upper bound; when we descend right, it becomes the new lower bound. An equivalent approach is to perform an inorder traversal and confirm the values come out in strictly increasing order, since inorder on a valid BST is always sorted.

Algorithm walkthrough

1. 1Call a helper on the root with an unbounded interval: low = -infinity and high = +infinity.
2. 2If the current node is null, it satisfies the rule vacuously, so return true.
3. 3If the node's value is not strictly greater than low or not strictly less than high, return false.
4. 4Recurse left with the interval (low, node.val), tightening the upper bound to the current value.
5. 5Recurse right with the interval (node.val, high), tightening the lower bound to the current value.
6. 6Return true only when both recursive checks succeed for every node.

Implementation

class Solution:
    def isValidBST(self, root: 'TreeNode') -> bool:
        def validate(node, low, high):
            if node is None:
                return True
            if not (low < node.val < high):
                return False
            return validate(node.left, low, node.val) and validate(node.right, node.val, high)

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