/**
 * An implementation of the basics of a binary search tree:
 * find, add, and toString.
 * This implementation does not attempt to keep the search tree balanced.
 * 
 * @author David Mutchler and YOUR-NAME-HERE.
 *         Created October, 2008.
 *         
 * @param <K> Type of the keys in this binary search tree.
 * @param <E> Type of the data associated with the keys in this binary search tree.
 */
public class BinarySearchTree<K extends Comparable<? super K>, E> {
	
	private class TreeNode {
		private K key;
		private E data;
		private TreeNode left;
		private TreeNode right;
	
		private TreeNode(K key, E data) {
			this.key = key;
			this.data = data;
			this.left = null;
			this.right = null;
		}

		/**
		 * Adds a node to the binary search tree with the given key and data,
		 * preserving the ordering in the binary search tree.
		 * If there is already a node in the binary search tree with the
		 * given key, replaces its data with the given data.
		 * 
		 * This implementation does NOT need to keep the tree balanced.
		 *
		 * @param keyToAdd Key for the node to be added to the binary search tree
		 * @param dataToAdd Data associated with the key to be added
		 */
		private void add(K keyToAdd, E dataToAdd) {
			// TODO: Replace this stub with correct code.
		}
		
		/**
		 * Returns the data in the node of the binary search tree
		 * with the given key, or null if there is no node with the given key.
		 *
		 * @param keyToFind Key for the node whose data is to be returned
		 * @return the data in the node of the binary search tree
		 *         with the given key,
		 *         or null if there is no node with the given key.
		 */
		private E find(K keyToFind) {
			// TODO: Replace this stub with correct code.
			return null;
		}
		
		/**
		 * Returns a string containing the keys of the binary search tree
		 * in sorted order (lowest to smallest).
		 * 
		 * @return a string containing the keys of the binary search tree
		 *         in sorted order (lowest to smallest).
		 */
		@Override
		public String toString() {
			// TODO: replace this stub with correct code.
			return null;
		}
	}

	private TreeNode root;
	
	/**
	 * Constructs an empty binary search tree.
	 */
	public BinarySearchTree() {
		this.root = null;
	}
	
	/**
	 * Adds a node to the binary search tree with the given key and data,
	 * preserving the ordering in the binary search tree.
	 * If there is already a node in the binary search tree with the
	 * given key, replaces its data with the given data.
	 * 
	 * This implementation does NOT need to keep the tree balanced.
	 *
	 * @param keyToAdd Key for the node to be added to the binary search tree
	 * @param dataToAdd Data associated with the key to be added
	 */
	public void add(K keyToAdd, E dataToAdd) {
		if (this.root == null) {
			this.root = new TreeNode(keyToAdd, dataToAdd);
		} else {
			this.root.add(keyToAdd, dataToAdd);
		}
	}

	/**
	 * Returns the data in the node of the binary search tree
	 * with the given key, or null if there is no node with the given key.
	 *
	 * @param keyToFind Key for the node whose data is to be returned
	 * @return the data in the node of the binary search tree
	 *         with the given key,
	 *         or null if there is no node with the given key.
	 */
	public E find(K keyToFind) {
		if (this.root == null) {
			return null;
		} else {
			return this.root.find(keyToFind);
		}
	}
	
	/**
	 * Returns a string containing the keys of the binary search tree
	 * in sorted order (lowest to smallest).
	 * 
	 * @return a string containing the keys of the binary search tree
	 *         in sorted order (lowest to smallest).
	 */
	@Override
	public String toString() {
		if (this.root == null) {
			return new String();
		} else {
			return this.root.toString();
		}
	}
}