Validate BST and In-Order Properties
Validate a binary tree as a BST using min/max bounds passed down the tree and by checking that in-order traversal produces a sorted sequence.
The BST Validation Problem
Validate BST (LeetCode #98) is a classic interview problem that trips up many candidates. The naive approach checks only that each node's value is greater than its left child and less than its right child, but this local check is insufficient. A subtree node might satisfy the local rule yet violate the global BST property. The correct solution propagates valid min/max bounds down the tree.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Why local check fails:
# 5
# / \
# 1 4
# / \
# 3 6
# Node 4's children (3, 6) satisfy local rule,
# but 4 < 5 and is in the RIGHT subtree -- BST violated!
print('Local check is insufficient -- use min/max bounds')Min/Max Bounds Approach
Pass lower and upper bounds down the recursion. At each node, verify that low < node.val < high. When recursing left, update the upper bound to node.val (left subtree must be less). When recursing right, update the lower bound to node.val (right subtree must be greater). Start with low = -infinity and high = +infinity.
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Valid BST:
valid = TreeNode(5)
valid.left = TreeNode(3)
valid.right = TreeNode(7)
print(is_valid_bst(valid)) # True
# Invalid BST (3 is in wrong subtree conceptually):
invalid = TreeNode(5)
invalid.left = TreeNode(1)
invalid.right = TreeNode(4)
invalid.right.left = TreeNode(3)
invalid.right.right = TreeNode(6)
print(is_valid_bst(invalid)) # False (4 < 5 in right subtree)All lessons in this course
- BST Insert and Search
- BST Delete: Three Cases
- Validate BST and In-Order Properties
- Kth Smallest, Range Sum, and BST to Sorted Array