Problem
Given the root of a binary tree, return true if it is a valid Binary Search Tree. Otherwise, return false.A valid BST must satisfy the following property for every node: all values in the left subtree must be smaller than the node's value, and all values in the right subtree must be greater than the node's value.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [2,1,3]
2
/ \
1 3
Output
true Input
root = [5,1,4,null,null,3,6]
5
/ \
1 4
/ \
3 6
Output
false Solution
This solution uses Depth-First Search (DFS) with recursion. Each node must lie within a valid range of values determined by its ancestors.For the root, the valid range is from negative infinity to positive infinity. When moving to the left child, the current node's value becomes the new upper bound. When moving to the right child, it becomes the new lower bound.
If any node falls outside its valid range, the tree is not a valid BST.
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) {
return true;
}
// Current node must be within the valid range.
if (node.val <= min || node.val >= max) {
return false;
}
// Validate left and right subtrees with updated bounds.
return validate(node.left, min, node.val)
&& validate(node.right, node.val, max);
}
Complexity
Each node in the binary tree is visited exactly once, resulting in a time complexity ofO(n).
The recursive call stack can grow up to the height of the tree, resulting in an extra space complexity of
O(h), where h is the height of the tree.