Validate Bst

from math import inf

def is_valid_bst(root):
    def check(node, low, high):
        if not node:
            return True       # empty is fine
        if not low < node.val < high:
            return False      # out of range
        return (check(node.left, low, node.val) and
                check(node.right, node.val, high))
    return check(root, -inf, inf)

Validate Binary Search Tree. Given a binary tree, decide if it's a valid search tree: everything in a node's left subtree is smaller, and everything in its right subtree is larger.

Here's our tree. Five at the root, two and eight below it, then one, four, three and nine.

The tempting check compares each node with its children. Five beats two and stays under eight; two and eight pass too. But three sits right of five, and three is smaller than five. Every ancestor counts.

So give each node an allowed range, low to high. The root allows anything. Going left, the high drops to the parent's value. Going right, the low rises to it. A value outside its range fails.

In code, a helper takes a node and its range. Empty is fine. If the value isn't strictly inside, return false. Otherwise check the left child with the value as high, and the right with it as low.

Let's walk it. Five, anything goes: pass. Two, under five: pass. One, under two: pass. Four, between two and five: pass. Eight, over five: pass. Three must be between five and eight. It isn't: fail. Make it a six, and every gate opens.

Each node is checked once: O of n time. The recursion goes as deep as the tree: O of h space. Another way: an in-order walk of a valid tree is strictly increasing. Ours reads five, then three.

Pass the range down, not just the parent. That's Validate Binary Search Tree.