CIS2168
FIFTEEN MINUTE TEST # 11
November 23, 2010

(10)	1. Explain by example why quicksort can take O(n*n) time.











(20)	2. Implement the function 
	public static <T extends Comparable<T>>boolean everyBranchContains(BinaryTree<T> root,
			T value) {
	   which returns true iff every branch from root to leaf contains the specified
	   value.














	



(20)	3. Implement the static function 
	private static <T extends Comparable<T>> void collect(Node<T> root, 
		ArrayList<T> a) 
	   which will add to a all the values in the tree rooted at root. 
	   Then use this function to implement the function
	public static <T extends Comparable<T>> T[] collect(BinarySearchTree<T> root) {
	   which returns an array containing in sorted order all the values in the binary 
	   tree rooted at root.