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

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

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:


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.