you will be given a binary tree represented as an array. Your job will be to verify if it is a binary search tree or not. Input will be given as a space-separated array representing a binary tree as we discussed in class, with the root node occupying the 0th index, the root node's children occupying indices 1 and 2, their children occupying indices 3-6, etc. All trees will be balanced, and will be filled left to right in the bottom layer.

Thus, if you are given the following input:

10 5 15 2 7 11 25 1

then you should print:

true since this tree is indeed a binary search tree. As another example, the

input

2 4 5

does not represent a binary search tree since the number 2 is less than both its children (4 and 5).

Restrictions:

Your algorithm must run in time O(n), where n is the number of nodes in the graph. Any algorithm that does not will be docked points for correctness as well as design. In addition, any algorithm that returns true on all possible inputs or false on all possible inputs will receive a grade of 0.

Read the assignment handout for a better description, as I was able to include a diagram. In this problem, you will be given a binary tree represented as an array. Your job will be to verify if it is a binary search tree or not. Input will be given as a space-separated array representing a binary tree as we discussed in class, with the root node occupying the Oth index, the root node's children occupying indices 1 and 2, their children occupying indices 3-6, etc. All trees will be balanced, and will be filled left to right in the bottom layer. Thus, if you are given the following input: 10 5 15 2 7 11 25 1 then you should print: true since this tree is indeed a binary search tree. As another example, the input 245 does not represent a binary search tree since the number 2 is less than both its children (4 and 5). Restrictions: Your algorithm must run in time O(n), where n is the number of nodes in the graph. Any algorithm that does not will be docked points for correctness as well as design. In addition, any algorithm that returns true on all possible inputs or false on all possible inputs will receive a grade of 0. Code for reading input and writing output has been provided in the assignment Binary Search TreeChecker; your job is to complete the isBinarySearch Tree() function. You may add whatever helper functions you'd like, but may not use any additional libraries. 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 tree int binaryTree; String input = sc. nextLine(); if (input . equals("")) { binaryTree = new int; } else { String binaryTreeStrings = input. split(" "); binaryTree = new int[binaryTreeStrings . length]; for (int i = 0; i