CIT 594 Binary Trees
Spring 2012, David Matuszek

Purposes:

To introduce binary trees.
To give you some experience reading and updating code.
To give you lots of practice with simple recursions.
To give you some practice with Java's built-in List and Set collections.

General Idea:

Back before Java had generics, I defined a BinaryTree class. Your job is to:

Update this class by genericizing it (making BinaryTree a generic class).
Implement a number of additional recursive methods. Some of these methods may be used in later assignments.

Details:

Supplied code: BinaryTree.java and BinaryTreeTest.java.

You will first need to "genericize" the BinaryTree class. Begin by changing

public class BinaryTree {
    public Object value;
    private BinaryTree leftChild;
    private BinaryTree rightChild;

public class BinaryTree<V> {
    public V value;
    private BinaryTree<V> leftChild;
    private BinaryTree<V> rightChild;

After this, add <V> to methods where appropriate, and change Object to V where appropriate. This may take some trial and error, until you get the hang of it. The goal is to eliminate all the warnings that Eclipse gives you.

Add the following methods to the BinaryTree class. For each method, begin by writing a JUnit test method. Then write the method stub, then test your JUnit test and make sure it fails, then write the method.

All public methods should have complete and accurate Javadoc comments. For the most part you can just copy the comments from this assignment, but be sure to also supply @param, @return, and @throws tags as appropriate. Add an @author tag to the class and update the @version.

All the required methods should be written recursively. Do not use loops. You can use additional helper methods, so long as they are private. In this case, either the required method or its helper method must be recursive.

In this implementation, as in most implementations of binary trees, you can only go down, to children; there is no way to go up, to a parent. (Of course, you could define a node in a binary tree to have a reference to its parent as well as to its left and right children; I'm just saying this isn't usually done.) So every node (that is, every instance of the BinaryTree class) can be considered to be the root of a binary tree. In order to understand the following methods, you must understand that every instance of a BinaryTree object can be thought of as a single node, or as the root node of a binary tree, or as representing the entire binary tree rooted at this node. Binary trees are composed of binary trees.

Thus, for example, one method you will be asked to write is numberOfNodes, which returns how many nodes there are in this binary tree, in other words, in the entire binary tree rooted at this node. If this binary tree occurs as part of some other binary tree, that fact is irrelevant; only this node and its descendents are reachable, and anything unreachable is irrelevant.

Note: A binary tree may be null. One or both of the children of a binary tree may be null. In most cases, this is perfectly acceptable; if there are any cases where it isn't, your method should throw a NullPointerException.

Note: Set and List are interfaces, not classes; but you can create instances of HashSet and ArrayList.

public BinaryTree<V> leftmostDescendant(): Returns the leftmost descendant of this binary tree. That is, return the leaf node that is the left child of the left child of ... the left child of this binary tree. If this binary tree has no left child, return this binary tree.
public BinaryTree<V> rightmostDescendant(): Returns the rightmost descendant of this binary tree. That is, return the leaf node that is the right child of the right child of ... the right child of this binary tree. If this binary tree has no right child, return this binary tree.
public int numberOfNodes(): Returns the total number of nodes in this binary tree (include the root in the count).
public int depth(): Returns the depth of this binary tree. The depth of a binary tree is the length of the longest path from this node to a leaf. The depth of a binary tree with no descendants (that is, just a leaf) is zero.
public boolean isBalanced(): Returns true if this binary tree is balanced, and false otherwise.
public boolean containsEqualValue(V value): Returns true if and only if some node in this binary tree contains a value that is equal to the parameter.
public boolean containsSameValue(V value): Returns true if and only if some node in this binary tree contains the same object (not just an equal object) as the one given for the value parameter.
public Set<BinaryTree<V>> leaves(): Returns a Set of all the leaves of this binary tree.
public Set<V> valuesOf(): Returns a Set of the values (of type V) in this binary tree.
public List<V> fringe(): Returns a List of the values (of type V) in the leaves of this binary tree, in left-to-right order.
public BinaryTree<V> copy(): Returns a new BinaryTree equal to (but not the same as) this binary tree. Every node in this new BinaryTree will be created by the copy method; values will be identical (==) to values in the given binary tree.
public BinaryTree<V> reverse(): Returns a new binary tree which is the mirror image of the binary tree whose root is at this binary tree. That is, for every node in the new binary tree, its children are in reverse order (left child becomes right child, right child becomes left child).
public void reverseInPlace(): Rearranges the binary tree rooted at this binary tree to be the mirror image of its original structure. No new BinaryTree nodes are created in this process.

Examples

Suppose you have the following binary tree:

and suppose the BinaryTree variable named root refers to the topmost node of this binary tree. Then:

Method call	Returned value
`root.leftmostDescendant()`
`root.rightmostDescendant()`
`root.numberOfNodes()`	`11`
`root.depth()`	`5`
`root.isBalanced()`	`false`
`root.containsEqualValue("G")`	`true`
`root.containsSameValue("G")`	`true` if the string `"G"` in the binary tree is the same (`==`) String "G" that is given as a parameter; `false` if they are in different memory locations, even if they are `equals()` to each other.
`root.leaves()`	The Set `{ }`
`root.valuesOf()`	The Set `{ "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K" }`
`root.fringe()`	The list `[ "K", "I", "J" ]`, with values in that order.
`root.copy()`	A reference to a duplicate of the binary tree `root`, with all new nodes.
`anotherTree = root.reverse()`	A new `BinaryTree`, with all new nodes, that looks like this:
`root.reverseInPlace()`	Same picture as the one immediately above, but no new BinaryTree nodes are created. Instead, the original tree is modified by swapping the contents of the `leftChild` and `rightChild` references.

Due date:

Your program is due before 6am Tuesday, January 31. Zip up your entire Eclipse project, and submit via Blackboard. Only assignments submitted via Blackboard will be accepted--any assignments emailed to me will be discarded without comment. A late penalty of 5 points per day (out of 100 points) will apply.

Because many of you are interviewing this semester, a limited number of 48-hour extensions will be available. To get an extension, email me before 5pm Friday, stating the reason you need the extension. No extensions will be granted after Friday. If you get an extension and fail to get the project in by the extended due date, late points will be counted from the original due date.