A Binary Search Tree (BST) is a special type of binary tree that maintains a specific ordering property. This property makes searching, insertion, and deletion operations very efficient - typically O(log n) in balanced trees.
The fundamental rule of a BST is that for every node:
The key insight for validation is that each node has a valid range of values it can contain. The root can be any value, but as we traverse down the tree, this range becomes more constrained.
When validating a BST, we need to track the minimum and maximum values allowed for each node. Initially, the root can have any value (negative infinity to positive infinity). But as we move:
This ensures that not only is each parent-child relationship correct, but the entire subtree maintains the BST property.
A naive approach might only check if left.val < parent.val < right.val for each node. However, this misses violations where a deep descendant breaks the BST property. For example, a node with value 6 in the left subtree of a node with value 5 would be invalid, even if 6's immediate parent is greater than 6.
1def validate_range(node, min_bound, max_bound):
2 # Base case: empty subtree is always valid
3 if not node:
4 return True
5
6 # Check if current node is within valid bounds
7 if node.val <= min_bound or node.val >= max_bound:
8 return False
9
10 # Recursively check subtrees with updated bounds
11 left_valid = validate_range(node.left, min_bound, node.val)
12 right_valid = validate_range(node.right, node.val, max_bound)
13
14 return left_valid and right_valid