The code language preferred is JAVA. with comments

In today’s Lab we will explore a specific way to perform avalidation check of whether a Binary Tree is actually a BinarySearch Tree (BST). You will implement this design by one of the twoways stated below:

[1] Performing a check of constraints on node values for eachsub-tree, just the way we discussed in the Lecture this week.Please remember what we discussed in the Lecture - that - for aBinary Tree to qualify as a Binary Search 1 Tree, we must peformthe node values check of-course but also must not forget the valuechecks at the sub-tree level.

[2] Performing the BST check by doing an In-Order Traversal ofthe Binary Tree as discussed in the Lecture.Since we know that anin-order traversal of a BST results in nodes being processed insorted order, as soon as there is a violation of sorted order wewould know that the tree provided is not a BST.

/* Class to represent Tree node */

class Node {

int data;

Node left, right;

public Node(int item) {

data = item;

left = null;

right = null;

}

}

The root element of the Binary Tree is given to you. Below is anillustrated sample of Binary Tree nodes for your reference, whichin-fact is the same example we discussed in the lecture.

tree.root = new Node(4);

tree.root.left = new Node(2);

tree.root.right = new Node(6);

tree.root.left.left = new Node(1);

tree.root.left.right = new Node(3);

tree.root.right.left = new Node(5);

tree.root.right.right = new Node(7);

Your code will need to return a boolean : True or False.

When you follow the validation process specified - thecomplexity of the solution will be as below.

Time Complexity: O(n) Space Complexity: O(n)

The linear space complexity would come from the recursion (AKA”recursion stack”) you employ to validate the Tree. Submissionsthat don’t meet the linear Time and Space complexities willonly