Code in Java Using the binary search tree (BST) data structure, we can sort a sequence of n elements by first calling an insertion procedure for n times to maintain a BST, and then performing an...

Code in Java

Using the binary search tree (BST) data structure, we can sort a sequence of n elements by first calling an
insertion procedure for n times to maintain a BST, and then performing an Inorder-Tree-Walk on the
BST to output the elements in sorted order.

In this programming assignment, you will implement in Java this sorting algorithm using BST, by using
the improved insertion procedure. Note that each node of a BST is an object containing four attributes:
key (for the value of an element), lef t (for its left child), right (for its right child), and p (for its parent).
Please add a static counter to track the number of key comparisons made by your algorithm. Your program
will output the following
1. The size of the input array,
2. The input array,
3. The list of array elements after sorting, and
4. The number of key comparisons made.