CSCI 151 - Lab 10
Binary Search Trees

Overview

In this lab, we will implement a Binary Search Tree and visualize the process of insertion and deletion.

Materials

Setup

  1. Download the skeleton for this project.
  2. Unpack the code into a new Eclipse Java project.

Description

We can efficiently store information with Lists, but determining if an element is present could take a linear search through each element if the data is not sorted. At best, sorting will take O(n log n), and so we explore an alternative here which incorporated the idea of binary search into a linked structure of nodes.

Our items to be stored and compared in this lab will be strings. For testing purposes, I recommend using single letters as entry, however, full words can also be used.

Methods that remain to be implemented in the BinarySearchTree class have been marked with TODO for easy identification.

Step 1 - TreeNode and Direction

First, review the provided code for a Direction Enum. There are three possible directions that could be useful as you navigate your BinarySearchTree. These can record if your algorithm just walked LEFT, RIGHT, or found the node you were looking for, denoted by AT.

The which function of Direction will return this status when given two comparable elements, the first of which is your new item, and the second is an element the tree.

Second, review the provided code for a TreeNode class. You will find many helpful methods contained in This classes. In particular, a TreeNode can

Step 2 - size

To gain familiarity with the different components of the lab, first write a method for a BinarySearchTree that will return the size of the root node. If there is no root, you should return 0.

Step 3 - insert

The next most useful method to implement is insert. To implement this process, create two temporary pointers into your tree, one for the parent, and one for the current node. Step through the tree until your current node is either identical to the item your are adding (AT) or you have fallen off the tree. When you fall off, use the parent of where you are, and the Direction you moved off, to add a new child to the parent.

Step 4 - contains

A BinarySearchTree can do a similar process to simply detect if an element is currently stored in the tree by either iteratively or recursively walking down the tree, following the child in the appropriate Direction at each step. If you find the element in the current node, return true. If you walk off the tree without finding the element in question, return false.

Step 5 - traversals

Implement each of the traversal algorithms discussed in class, pre-order, in-order, and post-order. The pre-order will return the information stored a the root first, and then recursively traverse the left child followed by the right child.

You might find it useful to create a helper method for your recursive method to augment the empty parameters of each method.

Step 6 - remove

Removal of TreeNodes in a BinarySearchTree is slightly tricky, but can be performed by the following algorithm.

Again, walk down the tree from the root, searching for the element to be removed. If you ever walk off the tree, you can stop the algorithm. However, if you find the element in the tree, you will encounter one of three cases.

  1. The element to be removed is a leaf. When this happens, there are no side-effects, and the parent should simply set the leaf in the indicated direction to be null.
  2. The element to be removed has one child. When this happens, the parent should bypass the child, and relocate its grandchild up one level.
  3. The element to be removed has two children. When this happens, the parent should find the immediate predecessor of this node. (Walk left once, then find the maximum child.) Replace the item at the current node with the item inside the immediate predecessor, and then repeat the removal process on the immediate predecessor.
Be sure to include a special case for detecting if the element to be removed in the root of your tree.

What to Hand In

Submit your BinarySearchTree.java implementation.

Grading

© Mark Goadrich, Hendrix College