• You will need a Tree class, with a Tree constructor which takes no parameters. Once again, use the default package (no package statement).

• Tree will need an insert(int x) method, which will insert the value x into your tree. For this tree, duplicate insertions should be discarded. That is, if I insert a value into the tree which is already in the tree, do not change your tree. Your method should return true if the element is added (which should happen if it isn't already in the tree), and false if it is not added (if the number was already in the tree).

• Tree will need a size(int x) method, will return the int size of the subtree rooted at the node that contains integer x. If x is not in the tree, it should return 0.

• You should create your own JUnit tests as well, in a file with a name ending in Test.java or Tests.java.

• In order to make some of your JUnit tests, you should build some 2-3 trees by hand, on paper, by calling insertion, and then search. Create some tests which make sure that your code gives you back exactly what you expect for those cases. It is really difficult to test your code for correctness if you don't actually test it. For correctness. Note: in your JUnit code, you can have "magic numbers" all over the place.

  Please consider the following: (a) How well do your tests cover your code? That is, is every line of your code tested by your test cases? For every conditional in your code, is it tested once when true, and once when false? (b) Does your code pass all of your tests? If not, why not? (c) Do you think your code works on cases you haven't tested? What might go wrong on a large test case, in which you don't want to work out the answer by hand? How can you test some of the things that might go wrong, without working it out by hand? (The answer does not involve getting the correct answer to a large instance.)

• Tree.java should be your main java file. Your JUnit test file should end in Test.java or Tests.java. You will only need those two files, though you may want to have some inner classes within your Tree.java file.
• To get you started, here are some very basic tests. They are not sufficient to test your code at all, but you should, at the very least, be able to pass the first one and run them all even if they don't pass. Pass the first 4, or all of them? You are doing really well.

 import static org.junit.Assert.*; import org.junit.Test; public class GivenTreeTests { @Test public void singleNodeTree() { Tree t = new Tree(); t.insert(9); assertEquals(1, t.size(9)); assertEquals(0, t.size(8)); assertEquals(0, t.size(10)); t.insert(15); assertEquals(2, t.size(9)); assertEquals(0, t.size(8)); assertEquals(0, t.size(10)); assertEquals(2, t.size(15)); assertEquals(0, t.size(18)); t = new Tree(); t.insert(15); t.insert(9); assertEquals(2, t.size(9)); assertEquals(0, t.size(8)); assertEquals(0, t.size(10)); assertEquals(2, t.size(15)); assertEquals(0, t.size(18)); } @Test public void oneSplitLeft() { Tree t = new Tree(); t.insert(9); t.insert(15); t.insert(1); assertEquals(3, t.size(9)); assertEquals(1, t.size(15)); assertEquals(0, t.size(17)); assertEquals(0, t.size(11)); assertEquals(1, t.size(1)); assertEquals(0, t.size(0)); assertEquals(0, t.size(3)); } @Test public void oneSplitRight() { Tree t = new Tree(); t.insert(1); t.insert(9); t.insert(15); assertEquals(3, t.size(9)); assertEquals(1, t.size(15)); assertEquals(0, t.size(17)); assertEquals(0, t.size(11)); assertEquals(1, t.size(1)); assertEquals(0, t.size(0)); assertEquals(0, t.size(3)); } @Test public void oneSplitMiddle() { Tree t = new Tree(); t.insert(1); t.insert(15); t.insert(9); assertEquals(3, t.size(9)); assertEquals(1, t.size(15)); assertEquals(0, t.size(17)); assertEquals(0, t.size(11)); assertEquals(1, t.size(1)); assertEquals(0, t.size(0)); assertEquals(0, t.size(3)); } @Test public void testDuplicates() { Tree t = new Tree(); t.insert(1); t.insert(9); t.insert(15); t.insert(13); t.insert(20); t.insert(7); t.insert(4); t.insert(1); t.insert(9); t.insert(15); t.insert(1); t.insert(9); t.insert(15); t.insert(13); t.insert(20); t.insert(7); t.insert(4); t.insert(13); t.insert(20); t.insert(7); t.insert(4); assertEquals(7, t.size(9)); assertEquals(3, t.size(4)); assertEquals(3, t.size(15)); assertEquals(0, t.size(12)); assertEquals(1, t.size(13)); assertEquals(0, t.size(14)); assertEquals(0, t.size(19)); assertEquals(1, t.size(20)); assertEquals(0, t.size(21)); assertEquals(1, t.size(1)); assertEquals(0, t.size(0)); assertEquals(0, t.size(3)); assertEquals(0, t.size(6)); assertEquals(1, t.size(7)); assertEquals(0, t.size(8)); } }