//Java program -> check if a given array is a binary search tree or not
/*---TEST CASES--------------------------------------------------------
Case 1: 2 4 5 FALSE
Case 2: 10 5 15 2 7 11 25 1 TRUE
Case 3: 50500 TRUE
Case 4: 90 50 150 20 75 95 175 5 25 66 80 92 111 166 200 TRUE
Case 5: 90 50 150 20 75 95 175 5 25 66 91 93 111 166 200 FALSE
Case 6: 8 4 12 2 6 10 14 1 3 5 99 9 11 13 15 FALSE
*/
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// parse the array representing the binary search binaryTreeObj
int[] binaryTree;
String input = sc.nextLine();
if (input.equals("")) {
binaryTree = new int[0];
} else {
String[] binaryTreeStrings = input.split(" ");
binaryTree = new int[binaryTreeStrings.length];
for (int i = 0; i < binaryTreeStrings.length; i++) {
binaryTree[i] = Integer.parseInt(binaryTreeStrings[i]);
}
// check if this is a binary search tree, print the result
System.out.println(isBinarySearchTree(binaryTree));
}
}
public static boolean isBinarySearchTree(int[] binaryTree) {
//TODO fill this in, along with any deeded helper fuctions
Main binaryTreeObj = new Main();
try {
binaryTreeObj.root = new CurrentNode(binaryTree[0]);
binaryTreeObj.root.left = new CurrentNode(binaryTree[1]);
binaryTreeObj.root.right = new CurrentNode(binaryTree[2]);
binaryTreeObj.root.left.left = new CurrentNode(binaryTree[3]);
binaryTreeObj.root.left.right = new CurrentNode(binaryTree[4]);
binaryTreeObj.root.right.left = new CurrentNode(binaryTree[5]);
binaryTreeObj.root.right.right = new CurrentNode(binaryTree[6]);
binaryTreeObj.root.left.left.left = new CurrentNode(binaryTree[7]);
binaryTreeObj.root.left.left.right = new CurrentNode(binaryTree[8]);
binaryTreeObj.root.left.right.left = new CurrentNode(binaryTree[9]);
binaryTreeObj.root.left.right.right = new CurrentNode(binaryTree[10]);
binaryTreeObj.root.right.left.left = new CurrentNode(binaryTree[11]);
binaryTreeObj.root.right.left.right = new CurrentNode(binaryTree[12]);
binaryTreeObj.root.right.right.left = new CurrentNode(binaryTree[13]);
binaryTreeObj.root.right.right.right = new CurrentNode(binaryTree[14]);
binaryTreeObj.root.left.left.left.left = new CurrentNode(binaryTree[15]);
binaryTreeObj.root.left.left.left.right = new CurrentNode(binaryTree[16]);
} catch (ArrayIndexOutOfBoundsException ex1) {
//ex1.printStackTrace();
} catch (UnsupportedOperationException ex2) {
throw new UnsupportedOperationException();
}
return checkIsBST(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
static CurrentNode root; //Root of the Binary Tree
/* Returns true if the given tree is a BST and its
values are >= min and <= max. */
static boolean checkIsBST(CurrentNode node, int min, int max) {
if (node == null) {
return true;
}
if (node.data < min || node.data > max) {
return false;
}
return (checkIsBST(node.left, min, node.data - 1)
&& checkIsBST(node.right, node.data + 1, max));
}
}
/* Class containing left and right child of current node and key value*/
class CurrentNode {
int data;
CurrentNode left, right;
// Constructor
public CurrentNode(int item) {
data = item;
left = right = null;
}
}