Description
Check that every node strictly exceeds all values in its left subtree and is smaller than all values in its right subtree.
Solution
import sys
sys.setrecursionlimit(100_000)
def is_valid_bst(root):
def check(node, low, high):
if not node:
return True
return low < node.val < high and check(node.left, low, node.val) and check(node.right, node.val, high)
return check(root, float('-inf'), float('inf'))Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,1,3]]- Output
true
All left values are smaller and right values larger.
Example 2
- Input
[[5,1,7,null,null,4,8]]- Output
false
4 violates the lower bound imposed by ancestor 5.
Example 3
- Input
[[2,2]]- Output
false
Duplicate values violate strict ordering.
Approach
Pass an allowed open interval down the recursion and narrow it at each node.
Time & space
O(n) time; O(h) recursion space. Here n is the node count, and h is the tree height.