Part 1: Measuring Inefficiency (40%)

In class, we analyzed the add method for the BinaryTree class. Because each recursive call involves counting the number of nodes in each subtree (an O(N) operation) and the number of calls depends upon the height of the tree (which will be roughly log N in a balanced tree), adding an item using this method will be O(N log N). Design a program that will verify this analysis experimentally (you may use the StopWatch class from HW3). Provide statistics from executions of your program and a coherent argument as to why the statistics support the claim that add is O(N log N).

Part 2: Additional Methods (60%)

Add the following methods to the BinaryTree class:

isLeaf(E item)	Returns true if the item appears in a leaf node of the tree; else false.
isParent(E item)	Returns true if the item appears in a non-leaf node of the tree; else false.
numLeaves()	Returns the number of leaf nodes in the tree.
numParents()	Returns the number of non-leaf nodes in the tree.
height()	Returns the height of the tree, i.e., the length of the longest path from the root to a leaf.
weight()	Returns the weight of the tree, i.e., the sum of all the node depths.

You should include a main method in your modified BinaryTree class that tests each of these methods. Part of your grade will depend upon the thoroughness of your tests.