copyright Steve J. Hodges

CS21 Spring 2018

Assignment 7

Binary Search Tree

Directory Name


Required Executable Name


I'll run your program either way:
java p7

Program Description

Implement a Binary Search Tree data structure in C++ or Java. Your bst will store integers. (For convenience, you may store the data directly in the linknode if you wish.) Your bst should implement the following public functions:

You should also implement, at your discretion, any helper or wrapper functions. You may assume that the key values are unique.


Create a main program that reads a "session trace" from STDIN and sends output to STDOUT. The input will contain (at most) one operation per line. Apply, in order, each of the operations to an object of your bst class. Ignore any comments in the input. A comment begins with a pound sign ("#") and continues to the end of the line.

Sample Run

an   input session trace
matching   output session trace


Each of the following functions should generate output (one per line)

What to turn in

Put all of the source code files (.cpp, .h, makefile if approprite, .java, etc.) but no executeables, binaries, compiler, or data files (omit .o, "a.out" , .class files etc.) in a folder named as shown above in the home directory of your account on pengo. Please don't include any sub-folders.