import java.util.Collection;
/**
 * Binary search tree, keyed by K with data D, which
 * allows for insertion of the same key twice (or more), and will create
 * a new node for it each time.  The new node may be either to
 * the right or to the left of a higher node with the same
 * key; the direction for a duplicate key
 * is chosen at random, else duplicate keys
 * could create very long chains and hamper performance (or even
 * cause stack overflow errors on recursion).
 * Has a special search, which returns a collection
 * of data for all the keys within range.
 * 
 * @author reyzin
 *
 * @param <K> the type of keys, must be comparable with K or its superclass
 * @param <D> the type of data
 */

// AS YOU IMPLEMENT THIS CLASS, YOU MAY USE (WITH PROPER ATTRIBUTION)
// ANY CODE FROM LECTURES AND THE TEXTBOOK
// 40 POINTS TOTAL

public class BSTWithDuplicates <K extends Comparable<? super K>, D> {
	private class TreeNode {
		K key;
		D data;
		TreeNode left, right;
		// ADD MEMBERS AND CONSTRUCTORS AS NEEDED
	}

	// ADD MEMBERS AS NEEDED
	
	/**
	 * Adds (key, data) pair to the tree, even if the same key
	 * already exists.
	 * @param key
	 * @param data
	 */
	public void insert (K key, D data) {
// 10 POINTS
		// REMEMBER TO CHOOSE DIRECTION AT RANDOM (50-50) IN CASE TWO KEYS ARE EQUAL
		// USE Math.random()
		// IF YOU DON'T, YOU ARE LIKELY TO GET A STACK OVERFLOW
		// WHEN YOU DO A SEARCH, BECAUSE YOUR TREE WILL GET RIDICULOUSLY DEEP
		// BECAUSE OF ALL ENTRIES WITH KEY = 1
		// USE PRIVATE METHODS AS NEEDED
		
	}




	/**
	 * @param low
	 * @param high
	 * @return a collection of all data elements whose keys are between low and high (inclusive)
	 */
	public Collection<D> rangeSearch (K low, K high) {
// 20 POINTS 
		// BE EFFICIENT -- MAKE SURE NOT TO GO DOWN SUBTREES IN WHICH
		// NOTHING BETWEEN LOW AND HIGH CAN POSSIBLY LIE
		// USE PRIVATE METHODS AS NEEDED
		
	}



	/**
	 * @return the largest key in the tree, null if tree is empty
	 */
	public K maxKey() {
// 10 POINTS	
		// USE PRIVATE METHODS AS NEEDED
		// BE AS EFFICIENT--DON'T TRAVERSE THE WHOLE TREE, FOR EXAMPLES
	}

}