CSC 207  Grinnell College  Spring, 2012 
Algorithms and ObjectOriented Design  
This lab considers a binary search tree as a specific type of tree and provides practice with how such a tree structure might be implemented in Java.
Review the readings for this lab regarding the basic defintions of general trees and binary search trees.
Which of the following trees is(are) a binary search tree(s)?
The implementation of a binary search tree in Java follows a similar approach to our implementation of lists.
A node in the binary search tree is considered an object of a TreeNode class.
The data within a node in the tree (class TreeNode) is a generic data type.
A BSTree class combines the nodes into an overall structure. In this lab, we consider the following operations:
The BSTree class implements a binary search tree, including several methods already identified.
The binary search tree structure can be tested with the school directory as a application using the DirectoryBST class.
This lab's readings discuss the approaches and implementations for each of these Java classes.
Import the following classes into a trees package within eclipse.
Compile and run the tests provided within DirectoryBST.
What can you say about the order of the entries printed by the print method? Explain why this sequence is obtained.
The discussion of insertion into a binary search tree in the reading for this lab described the insertion of the number 153 into the following tree (which repeats the tree given above).
Suppose a similar insert method was used to build the tree in the above example (with numbers 23, 37, 48, 96, 123, 185, 200, 285, and 309 rather than names and entries).
Explain your answers.
Given the order of insertions in the main method of DirectoryBST, draw a picture of the binary search tree that is produced by that program.
Write an iterative version of the recursive lookup method.
Use ideas from print
to write a
printLeaves method, which prints just the leaves within a
tree. Here, one can still traverse the full tree  but printing should
occur only if a node has only null left and right subtrees.
Ideas from print also can be used to count the number of (non null) nodes in a tree. Use this approach to write a countNodes method.
The height of a tree is the maximum number of levels of nodes within the
tree; by convention, the height of a tree with only one node is 0. Thus,
the binary search tree shown between parts 4 and 5 above (with root 123)
has height 3. Add to the BSTree class a method
height
which computes the height of a tree.
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/207.sp12/labs/labintrotrees.shtml
created 18 April 2000 last revised 24 March 2005 last revised 45 April 2012 

For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. 