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 (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) {...}
   

   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:

   1. 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
      

   2. Draw the binary search tree resulting from removing Pete from the binary search tree in A.

   3. Draw the binary search tree resulting from removing John from the binary search tree in B.

   4. Draw the binary search tree resulting from removing Lon from the binary search tree in C.

   5. Draw the binary search tree resulting from removing Matt from the binary search tree in D.

Additional Questions

1. Write the body for the following static, generic method that removes and returns the smallest (left-most) label in the given binary search tree (a BinaryTree<T>).

   /**
    * Removes and returns the smallest (left-most) label in {@code t}.
    * 
    * @param <T>
    *            type of {@code BinaryTree} labels
    * @param t
    *            the {@code BinaryTree} from which to remove the label
    * @return the smallest label in the given {@code BinaryTree}
    * @updates t
    * @requires IS_BST(t)  and  |t| > 0
    * @ensures <pre>
    * IS_BST(t)  and  removeSmallest = [the smallest label in #t]  and
    *  labels(t) = labels(#t) \ {removeSmallest}
    * </pre>
    */
   public static <T> T removeSmallest(BinaryTree<T> t) {...}