CIT
594 Assignment
3: Exercises in RecursionSpring 2008, David Matuszek |

- To give you some experience writing generic classes and methods.
- To give you a lot of practice with recursion.
- To give you some practice with the
`Set`

collection.

Back before Java had generics, I defined a `BinaryTree`

class.
Your job is to:

- Genericize this class and the methods in it, and
- Implement a number of additional recursive methods. Some of these methods may be used in later assignments.

**Supplied code:**
BinaryTree.java and
BinaryTreeTest.java.

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

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

After this, addpublic class BinaryTree<V> { public V value; private BinaryTree<V> leftChild; private BinaryTree<V> rightChild;

`<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 IDE should help you do this.)
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.)

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 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 BinaryTree 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**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**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 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.

Please zip up and turn in your completed program, including * all*
Java source and class files and all Javadoc generated documentation, via Blackboard,
before midnight

`JohnSmith_Recursion.zip`

.