Binary Trees/Practice/Validate Binary Search Tree
Validate Binary Search Tree - Bounds Explained
Validate every node against a valid range, not just its children. Recurse carrying (low, high) bounds: the left child inherits the same low but a new upper bound of the parent, the right child inherits a new lower bound - and anything outside its range fails.
Why it works
A BST constraint is about whole subtrees, not adjacent pairs: a node deep on the left must still be smaller than a distant ancestor on the right. Carrying explicit bounds threads that distant constraint down the tree in a single O(n) pass.
The problem
Given the root of a binary tree, determine if it is a valid binary search tree (BST). A BST requires that for every node, all left descendants are strictly less and all right descendants are strictly greater.
Hints
- A naive check (left.val < root.val) is insufficient - think about the full subtree.
- Pass a valid range (min_val, max_val) down to each recursive call.
- Left child must be < root.val AND within inherited upper bound.
- Right child must be > root.val AND within inherited lower bound.
Test cases
| Input | Expected |
|---|---|
is_valid_bst([2,1,3]) | True |
is_valid_bst([5,1,4,null,null,3,6]) | False |
Reference starter code
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_valid_bst(root):
# Pass min/max bounds through recursion
pass
# Valid BST: [2,1,3]
r1 = TreeNode(2, TreeNode(1), TreeNode(3))
print(is_valid_bst(r1)) # True
# Invalid: [5,1,4,None,None,3,6]
r2 = TreeNode(5, TreeNode(1), TreeNode(4, TreeNode(3), TreeNode(6)))
print(is_valid_bst(r2)) # False
More challenges in this topic
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.