ValidBST.java

amitsen01ei

Nov 20th, 2023

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

Java 1.30 KB | Source Code | 0 0

raw download clone embed print report

public class ValidBST {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
/**
* Checks if a binary tree is a valid binary search tree (BST).
*
* Time Complexity: O(n), where n is the number of nodes in the tree.
* As in the the worst case, we have to visit and check every node in the tree once.
*
*
* Space Complexity: O(h), where h is the height of the tree.
* This space is used by the call stack during the recursive calls.
*
* @param node the current node being checked.
* @param lower the lower bound for the value of the current node.
* @param upper the upper bound for the value of the current node.
* @return true if the subtree rooted at the given node is a valid BST, false otherwise.
*/
private boolean isValidBST(TreeNode node, long lower, long upper) {
if (node == null) {
return true;
}
if (node.val() <= lower || node.val() >= upper) {
return false;
}
return isValidBST(node.left(), lower, node.val()) && isValidBST(node.right(), node.val(), upper);
}
private record TreeNode(int val, TreeNode left, TreeNode right) {
}
}

Add Comment

Please, Sign In to add comment