CMPT 225 Assignment 3: Trees

In this assignment you are to implement (in C++) a pointer-based binary search tree to store and retrieve customer data.

Start by downloading the assignment files. This zipfile contains a makefile, a test script and ground truths, and stubs for all of the .h and .cpp files you need.

Customer Class

Customer.h, Customer.cpp

The customer class represents a customer of some fictional enterprise. The customer class should have the following attributes:

And these methods:
Customer c("Doe", 'J', 3344);
cout << c;
should print:
Doe, J. (3344)
It is very important that your output looks exactly like this. The auto-grading script will require this output to function properly.

You can find some basic instruction on how to overload the comparison operators and the cout << operator in this lab activity.

Binary Search Tree

BSTree.h, BSTree.cpp

Implement a binary search tree that has the following methods, all methods should preserve the binary search tree property.

I expect that you will need to also implement a number of helper methods (which should be private).

Node Class

Node.h, Node.cpp

As part of the tree implementation you should implement a Node class. Each node should contain a Customer object, pointers to left and right children and (optionally) the parent.


customer_app.cpp (complete, no need to modify)

I have provided an application to maintain a collection of customers. It uses your binary search tree class as the collection's container. It allows users to do the following:

Note that this application will not function correctly until you have correctly implemented all the required methods in the Customer and BSTree classes.

Sample Files

Two sample files of customers are included in the zip file. I'd suggest using small_names.txt for your preliminary testing as it is small enough for you to work out exactly what is going on with it. You can use the larger one big_names.txt for further testing.

Automated Testing

test_driver.cpp,, *.gt

A test driver test_driver.cpp is provided. It takes a command-line argument that specifies which test case to run. The test script will run all of the test cases.

Please assert that the first two test cases pass before moving on to the others. The first case checks the Customer printing, and the second checks the inOrderPrint.

Manual Testing and Debugging

Assessment and Submission


You should submit your assignment online to the CourSys submission server. You should submit the following:

Please read the documentation on the submission site for further information. The assignment is due at 11:59pm on March 20.


The submitted files must build with the provided makefile and customer_app.cpp in order to receive marks. The assignment is worth 3% and marks are allocated to the assignment as follows:

Back to the CMPT 225 homepage.