Validate Binary Search Tree

How you get there

1. 1A node deep in the left subtree must still be less than the root.
2. 2So pass an allowed (low, high) range down and tighten it at each step.
3. 3Equivalently, an in-order traversal must be strictly increasing.

Solution

def is_valid_bst(root) -> bool:
    def check(node, low, high) -> bool:
        if not node:
            return True
        if not (low < node.val < high):
            return False
        return check(node.left, low, node.val) and check(node.right, node.val, high)

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

Time

O(n)

Space

O(h)

What goes wrong

Comparing each node only with its direct children misses violations further down the tree.