# Binary Search Trees and Traversals
### Objectives
There are three objectives to this assignment. First, you will gain experience in implementing generic, nested data structures (in this case, a *binary search tree*). Second, you will gain some additional practice in implementing recursive methods as well as their iterative counterparts. Last but not least, you will continue to practice the creation of unit tests.
This is a pretty short project, though you are encouraged to start early in case you run into problems setting up
maven, jUnit, or encounter difficulties with git or the implementation itself.
### ISearchTree Conceptualization
The interface for our binary search tree is called `ISearchTree` and is generic in `T`, the type of the elements it stores. We can conceptualize this object, binary-tree(T) — pronounced “binary tree of T” — as a recursively defined triple containing:
* data : T (i.e.: data ‘of type’ T)
* left, right : binary-tree(T)
When the search tree is initialized, the left and right subtrees are expected to be the empty-tree (this will correspond to **null** in your implementation). Additionally, the **binary search tree property**:
> for all *tr* of type binary-tree(T),
> if *y* is a left descendant of tr, then *y.data* < *tr.data*
> if *z* is a right descendant of tr, then *z.data* > *tr.data*
must be maintained throughout your implementation (even between method calls). Here’s a **snippet** of the `ISearchTree` interface (the full one is included in the assignment’s starter kit):
“`java
/** …
* @param
*/
public interface ISearchTree
/**
* Returns {@code true} if key {@code e} is contained in this search tree; {@code false} otherwise.
*
ensures true iff e is-in data-set(this); false otherwise
*/
boolean contains(T e);
/**
* Returns the root of {@code this} search tree with {@code e} added to the
* appropriate subtree.
*
* note: when implementing this recursive version of add,
* do not use the “search” method from the slides.
*
*
* requires e not-in data-set(this)
* ensures if old(this) = empty_tree then
* this = (e, empty-tree, empty-tree)
* else [element is added to the tree] and
* is-ordered(e, this) -- i.e.: the output tree
* is ordered w.r.t. element e
* @throws IllegalArgumentException if a duplicate key is added.
*/
ISearchTree
/**
* This is just an iterative version of the add method, same contract, same exceptions.
* @see #add(T) for the contract.
*/
ISearchTree
// traversals
String dumpPreorder();
String dumpPostorder();
/**
* Returns a string containing a pre-order traversal of this tree. Hint,
* this should just call and return the result of {@link #dumpPreorder()}.
*
* ensures toString = [the string containing the preorder traversal
* of this tree].
*/
String toString();
}
“`
Note that the implementation you provide does not need to account for duplicate keys. In fact, as part of the contract for `add`, you are to throw a `IllegalArgumentException` if a client tries to add a duplicate key to the tree.
## Getting Started
The first thing you should do as part of the implementation of this project is either get a version of `add` working **or** work on the `dumpPreorder()` method and override your implementation’s `.toString()` method to call it. If you wish to use the approach detailed in class for iteratively adding to the tree, you’ll need to add a `private` method in your implementation that searches for some element *e* in the tree. Here’s a basic informal contract for the `search` helper method discussed in class:
“`java
/**
* Returns the subtree whose data matches {@code e}. If it fails to find
* a node matching {@code e}, the method returns the closest parent node.
*/
private ISearchTree
“`
### jUnit
Next, once your `addIter` (or `add`) **and** `.toString()` is working, it’s a good time to start writing some unit tests (write them early!). The organization of your unit tests should be similar to the organization discussed in class and used in prior assignments (namely, tests go into their own “green” directory)
* You should write test cases for all of your methods (with the exception of mutators like `setLeft(..)`, `setRight(..)`, and getters like `orderer()`). Moreover, since `add` and `addIter` both effectively accomplish the same thing, you can reuse your expected inputs and outputs when testing these methods.
* You should write tests for boundary cases, routine cases, and any tests you consider challenging.
* Practice good unit testing methodology by breaking up your test cases (i.e.: don’t clump all of your jUnit asserts in a single `@Test` method, etc.)
* I won’t prescribe a fixed number of tests for you to write, use your best judgement on this — that said, you should have at least four (preferably more). Note that since I’m not requiring you to implement `delete(..)` there are fewer configurations the tree can be in, thus it is ok if you do fewer tests this time around.
## Submission
Make sure you periodically commit and push your work with the following git command sequence
> git commit -am “detail your most recent tweaks/changes here”
> git push origin main
(take particular note of the usage of `main`, as this is now our default branch).
Make sure you commit and push before the deadline (detailed in the assignment on canvas).