TreeNode(val, left=None, right=None) is in the starter. Keep it.
Implement is_valid_bst(root) -> bool. A tree is a valid BST when, for every node:
- every value in its left subtree is strictly less than the node's value,
- every value in its right subtree is strictly greater,
- and both subtrees are valid BSTs themselves.
An empty tree is valid. Values are any Python integers, including very large and very negative ones.
# 8
# / \
# 3 12
# / \
# 6 15
is_valid_bst(root) # False: 6 is in 8's right subtree but smaller than 8
Checking each node only against its direct children is not enough: the tree above passes that check.
The tree has up to 20,000 nodes and may be a chain up to 10,000 levels deep (the Python tests raise the recursion limit for you). Aim for O(n). Don't use a made-up sentinel like -2**31 for "no bound": such values can appear in the tree.
Show hint
Every node's value must lie in a range determined by all of its ancestors, not just its parent. Carry that range down as you walk the tree, or think about what an in-order traversal of a valid BST looks like.