Homework Binary Search Trees This homework is necessary preparation for the lab Consider the following definition IS BST that defines binary search trees and answer the questions below mathdefinitions pre IS BST tree binary tree of T boolean satisfies tree satisfies the binary search tree properties as described in the slides with the ordering reported by compareTo for T including that it has no duplicate labels pre 1 Write the body for the following static generic method that searches a given binary search tree t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 of type BinaryTree T for a given label x of type T and returns true if it finds it and false otherwise Note that the BinaryTree must be restored i e its outgoing value must be the same as its incoming value Make sure your implementation takes advantage of the fact that the given tree is a binary search tree Returns whether code x is in code t param T type of code BinaryTree labels param t the code BinaryTree to be searched param x the label to be searched for return true if t contains x false otherwise requires IS BST t ensures isInTree x is in labels t public static T extends Comparable T boolean isInTree BinaryTree T t T x BinaryTree T left t newInstance BinaryTree T right t newInstance boolean find false T root t disassemble left right if x compareTo root 0 find root equals x isInTree left x isInTree right x t assemble root left right return true The isInTree method has a new and interesting property the generic parameter T is required to extend Comparable T The java lang Comparable T interface defines only one method int compareTo T which allows us to compare two Ts to see if one is less than equal to or greater than the other returning a negative zero or positive result respectively Make sure you use this method in your solution to allow you to search only one of the subtrees 2 Using the binary search tree algorithms discussed in class and alphabetical order A Draw the binary search tree that would result from inserting the following sequence of items into an initially empty binary search tree Matt Zeke Pete Lon John Mei Larry Bess Merv Adam Kate B Draw the binary search tree resulting from removing Pete from the binary search tree in C Draw the binary search tree resulting from removing John from the binary search tree in D Draw the binary search tree resulting from removing Lon from the binary search tree in E Draw the binary search tree resulting from removing Matt from the binary search tree in A B C D