CS 284-A Data Structures — Spring 2022

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

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