1. Suppose that Rectangle is a subclass of Shape. Write a method that takes an array of Shapes and returns an array of Rectangles containing all rectangles from the source array.
2. Write a method that rotates an array of type T[]. The last element should move to the first position, and all other elements should move forward one position in the array.
3. Write a method that takes two arrays a and b of type T[] and returns true if a contains a contiguous subarray of b.Length elements, each of which is equal to the corresponding element in b. Can your method be generalized so that a has type T[] and b has type U[]?
4. Write a method that returns the sum of all values in a binary tree of integers.
5. Write a method that returns true if a binary search tree of values of type T contains any duplicate values.
6. Write a method that removes the largest value from a binary search tree of values of type T.
7. Write a method that copies a binary tree of integers, adding 1 to every value in the tree as it does so.
8. Write a method that tells how many values in a binary search tree of values of type T are greater than a given value v of type T.
9. Write a method that fills out a binary search tree of type T, adding nodes as necessary so that all leaves have the same height. Nodes added under a leaf with value v should all also have the value v.
10. Write a method that tests whether a binary tree fulfills the ordering requirements of a binary search tree.
11. Suppose that we'd like to implement the following interface in
such a way that the contains method will always
run in time O(log N), where there are N elements in the set. add
and remove may take arbitrarily long to run. What data
structure might you use? Write an implementation.
interface Set<T> {
void add(T val); // add a value to a set, if not already present
void remove(T val); // remove a value, if present in the set
bool contains(T val); // return true if val is in the set
}12. Consider the arithmetic expression class we saw in the tutorial. Write a method that simplifies an arithmetic expression using the identities i + 0 = i and i * 1 = i. For example, the expression ((0 + (3 + 0)) + (1 * 7)) should simplify to (3 + 7).