Problem
Given the root of a binary tree, determine if it is a valid binary search tree.
Example
Input: [2,1,3]
Output: trueSolution
Recursive with valid range. Each node must fall within (min, max). Update bounds for left and right children.
def is_valid_bst(root):
def validate(node, low, high):
if not node: return True
if node.val <= low or node.val >= high: return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root, float('-inf'), float('inf'))function isValidBST(root) {
function validate(node, low, high) {
if (!node) return true;
if (node.val <= low || node.val >= high) return false;
return validate(node.left, low, node.val) && validate(node.right, node.val, high);
}
return validate(root, -Infinity, Infinity);
}bool validate(TreeNode* node, long low, long high) {
if (!node) return true;
if (node->val <= low || node->val >= high) return false;
return validate(node->left, low, node->val) && validate(node->right, node->val, high);
}
bool isValidBST(TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long low, long high) {
if (node == null) return true;
if (node.val <= low || node.val >= high) return false;
return validate(node.left, low, node.val) && validate(node.right, node.val, high);
}Complexity
- Time: O(n)
- Space: O(h)
Explanation
Naive parent-only comparison fails on subtle cases. We must enforce that ALL ancestors’ bounds hold, not just the immediate parent.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?