CSCI 151 - Lab 10
Binary Search Trees
In this lab, we will implement a Binary Search Tree and visualize the process
of insertion and deletion.
- Download the skeleton for this project.
- Unpack the code into a new Eclipse Java project.
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.
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
Second, review the provided code for a TreeNode class. You will find
many helpful methods contained in This classes. In particular, a TreeNode can
- remove a child node when given a Direction
- set a child to be a new TreeNode
- set the item to be a new element
- calculate the size of a node based on the size of its children
- find the maximum child
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.
Be sure to include a special case for detecting if the element to be
removed in the root of your tree.
- 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.
- The element to be removed has one child. When this happens, the parent should bypass
the child, and relocate its grandchild up one level.
- 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.
What to Hand In
Submit your BinarySearchTree.java implementation.
- To earn a D, finish Steps 1 and 2.
- To earn a C, finish the above and Step 3 and 4.
- To earn a B, finish the above and Step 5.
- To earn a 100, finish the above and Step 6.
© Mark Goadrich, Hendrix College