copyright Steve J. Hodges

CS21 Spring 2019

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. Your bst should implement the following public functions:

You should also implement as many helper and private functions as needed. You may assume that the key values are unique, and don't make any other assuptions about the values. For convenience, you may perform output operations in the public tree functions, or you can design an efficient mechanism to do all of the output outside of the tree for a bit of extra credit.


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.