Audit the Index

medium

A database engine's index is supposed to be a binary search tree, but a buggy migration may have corrupted it. Your audit must certify the strict BST property: for every node, all keys in its left subtree are strictly smaller and all keys in its right subtree are strictly larger. No duplicates allowed.

Given the root of a binary tree, return True if it is a valid BST, else False. Beware the classic trap: each child comparing fine against its own parent is not enough — a grandchild can violate a grandparent.

Tests pass a level-order array; implement the core in _is_bst on real nodes.

Example 1

in values = [2, 1, 3]

out True

Example 2

in values = [5, 1, 4, null, null, 3, 6]

out False

4 sits in 5's right subtree but 4 < 5.

Example 3

in values = [5, 4, 6, null, null, 3, 7]

out False

Locally fine everywhere, but the 3 hides in 5's right subtree — a deep violation.

Constraints

· 0 <= number of nodes <= 10^4
· -2^31 <= node value <= 2^31 - 1
· strict inequalities — equal keys are invalid