CSci 2101: Binary Search Tree

JUnit Test code for Binary Search Tree

More tests are needed.

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;

public class TestBST {
	private BinarySearchTree<Integer,String> emptyTree = new BinarySearchTree<Integer,String>();
	private BinarySearchTree<Integer,String> eightNodesTree= new BinarySearchTree<Integer,String>();
	
	@Before
	public void setUp() {
		eightNodesTree.put(4,"apple");
		eightNodesTree.put(6,"banana");
		eightNodesTree.put(1,"strawberry");
		eightNodesTree.put(3,"kiwi");
		eightNodesTree.put(7,"lemon");
		eightNodesTree.put(10,"lime");
		eightNodesTree.put(6,"mango");
		eightNodesTree.put(8,"pear");
	}
	
	@Test
	public void TestEmpty() {
		assertTrue(emptyTree.isEmpty());
		assertEquals(0,emptyTree.size());
	}
	
	@Test
	public void TestNonEmpty() {
		emptyTree.put(4,"apple");
		assertFalse(emptyTree.isEmpty());
		assertEquals(1,emptyTree.size());
	}
	
	@Test
	public void TestPutGetRoot() {
		emptyTree.put(4,"apple");
		assertEquals("apple",emptyTree.get(4));
	}
	
	@Test
	public void TestGetFromEmpty() {
		assertNull(emptyTree.get(4));
	}	
	
	@Test
	public void TestGet() {
		assertEquals("strawberry",eightNodesTree.get(1));
		assertEquals("lemon",eightNodesTree.get(7));
	}	
	
	@Test
	public void TestGetNotThere() {
		assertNull(eightNodesTree.get(5));
	}	
	
	@Test (expected=NullPointerException.class)
	public void TestNullKey() {
		assertNull(eightNodesTree.get(null));
	}
	
	@Test
	public void TestSize() {
		assertEquals(8,eightNodesTree.size());
	}
	
	@Test
	public void TestClear() {
		eightNodesTree.clear();
		assertTrue(eightNodesTree.isEmpty());
		assertEquals(0,eightNodesTree.size());
		assertNull(eightNodesTree.get(4));
	}	
	
	// to-do: tests for remove, tree traversals
}

Starting code for binary search tree:

/**
 * Binary search tree stores values indexed by keys. Keys must be Comparable and
 * are organized based on their natural ordering (i.e. the ordering given by
 * their compareTo). Values can be of any object type. This tree implementation
 * is not balanced, i.e. it may behave as a linked list in the worst case. Keys
 * may be repeated. Somewhat modeled after Map<K,V> classes in the Java
 * Collections Framework
 * 
 * Author: Elena Machkasova For UMM CSci 2101 class.
 **/

public class BinarySearchTree<K extends Comparable<K>, V> {
	private BSTNode root = null;

	/**
	 * @return true if the tree is empty, false otherwise
	 **/
	public boolean isEmpty() {
		return true;
	}

	/**
	 * @return the number of elements in the tree
	 **/
	public int size() {
		return 0;
	}

	/**
	 * Adds a given value indexed with a given key to the tree according to the
	 * binary search structure
	 * 
	 * @param key
	 *            - the key of the given element
	 * @param value
	 *            - the value of the given element
	 */
	public void put(K key, V value) {

	}

	/**
	 * returns a value associated with the given key in this binary search tree.
	 * If multiple values are associated with this key, any one may be returned.
	 * If there is no element associated with this key, null is returned.
	 * 
	 * @param key
	 *            - the key to search for.
	 * @return - a value to which the specified key is mapped, or null if this
	 *         tree contains no mapping for the key
	 * @throws NullPointerException if the key is null        
	 */
	public V get(K key) {
		return null;
	}

	/**
	 * Removes an element with the given key. The resulting tree is a binary
	 * search tree. If there is no such key, the tree is unchanged. If there are
	 * multiple values associated with this key, only one is removed. Returns
	 * the value associated with this key or null if there is no such value.
	 * 
	 * @param key
	 *            - the key
	 * @return - a value to which the specified key is mapped, or null if this
	 *         tree contains no mapping for the key
	 * @throws NullPointerException if the key is null         
	 */
	public V remove(K key) {
		return null;
	}
	
	/**
	 * Clears all elements from a given tree.
	 * The resulting tree is empty.
	 */
	public void clear() {
		
	}

	private class BSTNode {
		public K key;
		public V value;
		public BSTNode left = null;
		public BSTNode right = null;

		// null key will generate a null pointer exception when 
		// a method (such as compareTo) is called on it. 
		// This is fine, according to the JCF specification.
		public BSTNode(K key, V value) {
			this.key = key;
			this.value = value;
		}

	}
}

CSci 2101 course web site.