CSCI 151 Lab 10: Binary Search Trees

Overview

This lab will give you experience implementing key methods of binary trees and binary search trees.

Step 1: Setup

Download the Eclipse project skeleton for this lab, which contains some starter code.
Extract the zip file and import it as a new Eclipse project.
Make sure you can run the BinarySearchTreeTest (the tests will not pass yet).
Make sure you can also run the BinaryTreeApp. However, it will not do much yet!

Step 2: Binary tree methods

As you can see, the BinaryTree class has a number of methods with missing implementations, which you should fill in. It would be a good idea to make a new class with a main method to test your implementations (though you do not have to turn it in). Some of them (e.g. the traversals) can also be tested using the BinarySearchTreeTest.

boolean hasLeft(): return true if the tree is non-empty and has a non-empty left child.
boolean hasRight(): similar to hasLeft.
boolean isLeaf(): test whether the tree is a leaf (i.e. it is non-empty but both children are empty).
BinaryTree<E> rightmost(): return a reference to the rightmost node in the tree.
int height(): compute the height of the tree, which is the length of the longest path from the root to any leaf. The height of the empty tree is -1; the height of a single leaf node by itself is 0.
ArrayList<E> inorder(), preorder(), and postorder()

Interlude: BinaryTreeApp

At this point you should be able to run the BinaryTreeApp and type values into the box to insert them into the tree. (Note that the values are treated as Strings, which can be surprising if you are expecting them to be ints: for example, "220" < "30" as Strings because '2' < '3'.) Once you get deletion from your BST working in Step 4, you will also be able to click on nodes to delete them from the tree.

Step 3: finding in a BST

There are three BinarySearchTree methods you should implement, all of which have to do with looking things up in a BST. Think carefully about how to avoid duplicating code!

See the comments on each method for more information.

BinaryTree<E> findSubtree(E data)
E find(E data)
boolean contains(E data)

Step 4: remove

As preparation for implementing deletion from a binary search tree, implement a method

void replaceWith(BinaryTree<E> other)

which replaces all the fields in this with the fields from other. (You can literally write this.isEmpty = other.isEmpty, this.left = other.left, and so on.) The point of doing this is that if we have a subtree t that we know we want to change, it is hard to get back to its parent in order to replace its left or right reference with a new tree. So instead, we can use the replaceWith method to simply replace all the fields, which means we have no need to change the reference from the parent.

Finally, write a method

public E remove (E data)

which removes the given data from the tree (if it exists). As discussed in lab, this works as follows:

Find the subtree whose root is to be removed (you can use findSubtree).
If it has no left child, replace it with its right child (using replaceWith), or vice versa. Note that this also takes care of the case when the thing to be removed is a leaf.
Otherwise, find the predecessor of the data to be removed: find the rightmost node to the left of the root (using rightmost); replace the data of the node to be removed with the data from its predecessor; and replace the predecessor with its left child (using replaceWith).