🎨Now live: Try our Free AI Image Generation Feature

Description
The task is to determine whether a given binary tree is a valid Binary Search Tree (BST). A BST is defined such that for each node, the left subtree only contains nodes with values less than the node's value, and the right subtree only contains nodes with values greater than the node's value.
Intuition
The key to solving this problem is to perform a depth-first traversal (in-order traversal) of the tree while validating each node against upper and lower bounds to ensure it satisfies the BST properties.
Approach
- Recursive Approach:
- Implement a recursive function that checks each node, passing down the valid range (
min
andmax
) that the node's value must fit within. - At each node, check if its value is within the current valid range. - Recursively check the left and right subtrees, updating the valid range accordingly. - Base Case:
- If a node is
None
, it is considered a valid BST subtree. - Edge Cases:
- Handle cases where the tree is empty (
root
isNone
).
Complexity
Time Complexity:
O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once.
Space Complexity:
O(h), where h is the height of the tree. This is due to the recursive stack space used by the function.
Code
C++
class Solution {
public:
bool isValidBST(TreeNode* root, TreeNode* minNode = nullptr, TreeNode* maxNode = nullptr) {
if (!root) return true;
if (minNode && root->val <= minNode->val) {
return false;
}
if (maxNode && root->val >= maxNode->val) {
return false;
}
return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
}
};
Python
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def is_valid(node, min_val, max_val):
if not node:
return True
if (min_val is not None and node.val <= min_val) or (max_val is not None and node.val >= max_val):
return False
return is_valid(node.left, min_val, node.val) and is_valid(node.right, node.val, max_val)
return is_valid(root, float('-inf'), float('inf'))
Java
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode node, Integer min, Integer max) {
if (node == null) {
return true;
}
if (min != null && node.val <= min) {
return false;
}
if (max != null && node.val >= max) {
return false;
}
return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}
}
JavaScript
var isValidBST = function (root, min = null, max = null) {
if (root == undefined) return true
if (min !== null && root.val <= min) {
return false
}
if (max !== null && root.val >= max) {
return false
}
var rLeft = isValidBST(root.left, min, root.val)
var rRight = isValidBST(root.right, root.val, max)
return rLeft && rRight
}