Dare2Solve
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.
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.
Recursive Approach:
min
and max
) that the node's value must fit within.Base Case:
None
, it is considered a valid BST subtree.Edge Cases:
root
is None
).O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once.
O(h), where h is the height of the tree. This is due to the recursive stack space used by the function.
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);
}
};
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'))
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);
}
}
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
}