## HW4: Binary Search Trees

We’ll be defining binary search trees (BSTs) in Java. Here’s the interface we expect you to produce:

```
public class BST<E extends Comparable<? super E>> {
// you'll want to define a Node type here
// ... but you have to design it yourself!
public BST();
public int size();
public int height();
public boolean isPerfect();
public boolean isDegenerate();
public E insert(E); // returns old element
public E lookup(E); // throws exception when not found
public boolean contains(E);
public E remove(E); // returns old element (or null if not found)
public static BST<Integer> makeDegenerate(int size);
public static BST<Integer> makePerfect(int height);
}
```

You will have to design and implement the binary tree node structure
yourself. There are two basic options: single `Node`

class, using
`null`

to represent empty nodes; or an interface and open recursion
with an `Empty`

and a `Node`

class.

## Core BST methods

`size()`

returns the number of nodes (0 for an empty tree, 1 for a singleton, etc.); should be O(n)`height()`

returns the maximum distance between the root and a leaf; should be O(n)- the empty tree has height 0
- a tree with just a root has height 1
- height is the number of levels

`insert(E tgt)`

takes some target element,`tgt`

, and puts it in the correct place in the tree; should be O(log n) on balanced trees and O(h) (where h is the height) in general- It may be the case that there is
some element
`old`

in the tree such that`old.equals(tgt)`

- You should return
`old`

in that case. - Otherwise, return
`null`

.

- It may be the case that there is
some element
`lookup(E tgt)`

takes some target element,`tgt`

, and finds the element`e`

in the tree such that`e.equals(tgt)`

; should be O(log n) on balanced trees and O(h) (where h is the height) in general- You should return
`e`

- Throw a
`RuntimeException`

(or some subclass of it) if there is no such element`e`

- You should return
`contains(E tgt)`

should return`true`

if something in the tree is`.equals`

to`tgt`

and false otherwise; should be O(log n) on balanced trees and O(h) (where h is the height) in general`remove(E tgt)`

should remove`tgt`

from the tree if it is found; should be O(log n)- Return
`null`

if`tgt`

is not in the tree

- Return

(The O(log n) limits above only apply to balanced trees, but we are not asking you to keep the tree balanced. That is, your methods might be slower on unbalanced trees—typically, O(h), where h is the height—but they should be logarithmic when the trees happen to be balanced.)

## Degenerate and perfect trees

We also ask you to define some methods concerning *degenerate* and
*perfect* trees.

- A binary tree is
*degenerate*when every node has at most one child, i.e., no node has two children. - A binary tree is
*perfect*when every node has two children and all leaves are of the same height; put another way, every internal node has degree two and every node has a direct sibling of the same height.

We’d like you to define predicates that detect when a tree is
degenerate or perfect, namely `isDegenerate()`

and `isPerfect()`

. We’d
also like you to write static methods that generate degenerate and
perfect trees. The interfaces are subtly different:

`makeDegenerate(int size)`

should generate a`BST<Integer>`

that has`size`

nodes and is degenerate.`makePerfect(int height)`

should generate a`BST<Integer>`

that is`height`

*tall*, and is perfect.

## Grading

As usual, there will be an autograder to test your code. You are free to define other helpers, but you must meet the public specification above for your code to compile.

Please don’t forget the Stevens honor pledge.