Medium Min/Max Bounds Trees
In plain English: Check whether a binary tree satisfies the BST rule (left < root < right) at every node.
Passing tightening (lo, hi) bounds down the tree catches violations that a simple left < root < right check at each node would miss.
Prompt
Check if a binary tree is a valid binary search tree.
Try to write it from scratch before scrolling down.
Solution
def is_valid_bst(node, lo=float('-inf'), hi=float('inf')):
if node is None:
return True
if node.val <= lo or node.val >= hi:
return False
return (is_valid_bst(node.left, lo, node.val) and # bounds tighten as we descend
is_valid_bst(node.right, node.val, hi))
# Test: [2,1,3] => True; [5,1,4,null,null,3,6] => False