/**
 * Binary search tree, containing items of type K,
 * which allows duplicates by having a counter in each node
 * (rather than inserting duplicate nodes)
 *
 * @param <K> the type of entries in the tree, must be comparable with K or its superclass
 */

// AS YOU IMPLEMENT THIS CLASS, YOU MAY USE (WITH PROPER ATTRIBUTION)
// ANY CODE FROM LECTURES AND THE TEXTBOOK
// 30 POINTS TOTAL
public class CountingTree <K extends Comparable<? super K>> {

	private class TreeNode {
		K key;
		int count; // how many times key appears in the tree
		TreeNode left, right;
		//	ADD CONSTRUCTOR(S) AS NEEDED
	}

	private TreeNode root = null;
	private int totalEntries = 0; // total of all counts
	private int distinctEntries = 0; // number of nodes

	/**
	 * @return number of total entries (i.e., total of all counts)
	 */
	public int getTotalEntries() {return totalEntries;}

	/**
	 * @return number of distinct entries (i.e., number of nodes)
	 */
	public int getDistinctEntries() {return distinctEntries;}

// 10 POINTS EACH FOR insert and search below
	
	/**
	 * Inserts key into the tree.  If key is already in,
	 * just increments the corresponding counter.  If not,
	 * creates a new node.
	 * @param key the value to be inserted
	 */
	public void insert (K key) {
	}

	/**
	 * @param key
	 * @return number of times key is in the tree, i.e., the count of key (0 if key not in the tree)
	 */
	public int search (K key) {
	}




	/**
	 * Creates and returns a new tree, which allows lookup
	 * of entries in this tree by their counts.  Thus, in the new
	 * tree keys are integers, and data is K.  The new tree has as
	 * many nodes as the current tree.  The new tree must allow
	 * insertion of nodes with duplicate keys, since counts may repeat.
	 * @return the new tree
	 */
	public BSTWithDuplicates<Integer, K> frequencyTree () {
// 10 POINTS; USE PRIVATE METHODS AS NEEDED
	}

}