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).
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.