Validate a Binary Search Tree
Difficulty: Medium · Pattern: Tree DFS · Concept: Algorithms & Data Structures — Core Data Structures
A binary search tree (BST) requires, for every node: everything in its left subtree is strictly less than it, and everything in its right subtree is strictly greater — not just its immediate children, its entire subtree.
The classic mistake: checking only node.left.val < node.val < node.right.val at each node. That's necessary but not sufficient — a tree can look locally fine at every parent-child pair and still be an invalid BST overall, if some deeper descendant violates a constraint from an ancestor further up, not its immediate parent.
Your task: implement is_valid_bst(root), returning True/False. An empty tree (None) counts as valid.