import junit.framework.TestCase;

/**
 * A JUnit test case class.
 * Every method starting with the word "test" will be called when running
 * the test with JUnit.
 */
public class BSTNodeTest extends TestCase {

	// insert into an empty tree
	public void testInsert_a(){
		BSTNode tree1 = new BSTNode("a", "a-val");
		assertEquals(tree1.toString(), "[(a,a-val)[][]]");
	}
	// insert a node as a right branch from the root
	public void testInsert_ab(){
		BSTNode tree1 = new BSTNode("a", "a-val");
		tree1 = tree1.insert("b", "b-val");
		assertEquals(tree1.toString(), "[(a,a-val)[][(b,b-val)[][]]]");
	}
	// insert a node as a right branch from a node that is not the root
	public void testInsert_abc(){
		BSTNode tree1 = new BSTNode("a", "a-val");
		tree1 = tree1.insert("b", "b-val");
		tree1 = tree1.insert("c", "c-val");
		assertEquals(tree1.toString(), "[(a,a-val)[][(b,b-val)[][(c,c-val)[][]]]]");
	}
	// insert a node as a left branch from the root
	public void testInsert_cb(){
		BSTNode tree1 = new BSTNode("c", "c-val");
		tree1 = tree1.insert("b", "b-val");
		assertEquals(tree1.toString(), "[(c,c-val)[(b,b-val)[][]][]]");
	}
	// insert a node as a left branch from a node that is not the root
	public void testInsert_cba(){
		BSTNode tree1 = new BSTNode("c", "c-val");
		tree1 = tree1.insert("b", "b-val");
		tree1 = tree1.insert("a", "a-val");
		assertEquals(tree1.toString(), "[(c,c-val)[(b,b-val)[(a,a-val)[][]][]][]]");
	}
	// insert a node on both sides of the root
	public void testInsert_bac(){
		BSTNode tree1 = new BSTNode("b", "b-val");
		tree1 = tree1.insert("a", "a-val");
		tree1 = tree1.insert("c", "c-val");
		assertEquals(tree1.toString(), "[(b,b-val)[(a,a-val)[][]][(c,c-val)[][]]]");
	}
	// delete the root, which has one right child
	public void testDelete_abc_a(){
		BSTNode tree1 = new BSTNode("a", "a-val");
		tree1 = tree1.insert("b", "b-val");
		tree1 = tree1.insert("c", "c-val");
		tree1 = tree1.delete("a");
		assertEquals(tree1.toString(), "[(b,b-val)[][(c,c-val)[][]]]");
	}
	// delete a node not at the root with one right child
	public void testDelete_abc_b(){
		BSTNode tree1 = new BSTNode("a", "a-val");
		tree1 = tree1.insert("b", "b-val");
		tree1 = tree1.insert("c", "c-val");
		tree1 = tree1.delete("b");
		assertEquals(tree1.toString(), "[(a,a-val)[][(c,c-val)[][]]]");
	}
	// delete a right branch leaf
	public void testDelete_abc_c(){
		BSTNode tree1 = new BSTNode("a", "a-val");
		tree1 = tree1.insert("b", "b-val");
		tree1 = tree1.insert("c", "c-val");
		tree1 = tree1.delete("c");
		assertEquals(tree1.toString(), "[(a,a-val)[][(b,b-val)[][]]]");
	}
	// delete a left branch leaf
	public void testDelete_cba_a(){
		BSTNode tree1 = new BSTNode("c", "c-val");
		tree1 = tree1.insert("b", "b-val");
		tree1 = tree1.insert("a", "a-val");
		tree1 = tree1.delete("a");
		assertEquals(tree1.toString(), "[(c,c-val)[(b,b-val)[][]][]]");
	}
	// delete a node not at the root with one left child
	public void testDelete_cba_b(){
		BSTNode tree1 = new BSTNode("c", "c-val");
		tree1 = tree1.insert("b", "b-val");
		tree1 = tree1.insert("a", "a-val");
		tree1 = tree1.delete("b");
		assertEquals(tree1.toString(), "[(c,c-val)[(a,a-val)[][]][]]");
	}
	// delete the root, which has one left child
	public void testDelete_cba_c(){
		BSTNode tree1 = new BSTNode("c", "c-val");
		tree1 = tree1.insert("b", "b-val");
		tree1 = tree1.insert("a", "a-val");
		tree1 = tree1.delete("c");
		assertEquals(tree1.toString(), "[(b,b-val)[(a,a-val)[][]][]]");
	}
	// delete a root with two children
	public void testDelete_bac_b(){
		BSTNode tree1 = new BSTNode("b", "b-val");
		tree1 = tree1.insert("a", "a-val");
		tree1 = tree1.insert("c", "c-val");
		tree1 = tree1.delete("b");
		assertEquals(tree1.toString(), "[(c,c-val)[(a,a-val)[][]][]]");
	}
	// delete a root with two children and the replacement node is not a leaf
	public void testDelete_bafcd_b(){
		BSTNode tree1 = new BSTNode("b", "b-val");
		tree1 = tree1.insert("a", "a-val");
		tree1 = tree1.insert("f", "f-val");
		tree1 = tree1.insert("c", "c-val");
		tree1 = tree1.insert("d", "d-val");
		tree1 = tree1.delete("b");
		assertEquals(tree1.toString(), "[(c,c-val)[(a,a-val)[][]][(f,f-val)[(d,d-val)[][]][]]]");
	}

}