Question

The code is in JAVA

Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Instructions: Open CheckBST.java Implement isValidBST() Output: false true

public class CheckBST {

  //method to implement
public static boolean isValidBST(TreeNode root) {

}

public static void main(String[] args) {
TreeNode a = new TreeNode(1);
TreeNode b = new TreeNode(2);
TreeNode c = new TreeNode(3);
a.left = b;
a.right = c;
System.out.println(isValidBST(a));

TreeNode d = new TreeNode(2);
TreeNode e = new TreeNode(1);
TreeNode f = new TreeNode(3);
d.left = e;
d.right = f;
System.out.println(isValidBST(d));
}
}

TreeNode.java

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}

Answer 1

//create class TreeNode.java

class TreeNode {

int val;
TreeNode left;
TreeNode right;

TreeNode() {
}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
---------------------------------------------------------------------------------------------------------------------------------------------------

CheckBST.java

public class CheckBST {

//method to implement
public static boolean isValidBST(TreeNode root) {
  
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

static boolean isBST(TreeNode node, int min, int max) {
/* an empty tree is BST */
if (node == null) {
return true;
}

/* false if this node violates the min/max */
if (node.val < min || node.val > max) {
return false;
}

/* otherwise check the subtrees recursively tightening the min/max constraints */
// Allow only distinct values
return (isBST(node.left, min, node.val - 1)
&& isBST(node.right, node.val + 1, max));
}

public static void main(String[] args) {
TreeNode a = new TreeNode(1);
TreeNode b = new TreeNode(2);
TreeNode c = new TreeNode(3);
a.left = b;
a.right = c;
System.out.println(isValidBST(a));

TreeNode d = new TreeNode(2);
TreeNode e = new TreeNode(1);
TreeNode f = new TreeNode(3);
d.left = e;
d.right = f;
System.out.println(isValidBST(d));
}
}
---------------------------------------------------------------------------OUTPUT------------------------------------------------------------------