CSC 148 H1, Winter 2013

Exercise 6

Due: before noon on Friday 22 March 2013

Pre-marking: first run begins at noon on Wed. 20 Mar.; second run begins at noon on Thu. 21 Mar.

There are two parts to this exercise. For each part, there is a single file you must submit — make sure that you read the submission instructions carefully!

Important general advice

BEFORE you begin coding, make sure that you understand everything in this handout. Remember that the point of these exercises is not to get a "working" program by any means necessary — it is to ensure that you understand how to write the desired code. If you succeed in writing something that works but you do not understand why, then you have failed, no matter what grade you receive!

In particular, if there is something you do not quite understand, please, for your own sake, take the time to read the online textbook and the course notes and readings, then ask on the course forum or during office hours.


For this lab, you will work on code for Binary Search Trees. Please review the lecture material on this topic before you start the lab. In particular, read the code posted on the course website carefully: it contains many additional comments to explain what it is doing and why.

Download the file "" from the course website and make two separate copies of this file: one named "" and the other named "". You will be adding code to these files.


Implement method __contains__ in class BST in file, without using recursion. (You will get an automatic zero for this part if you use any form of recursion in your answer.)

This will be worth fewer marks because it is meant to be very easy, particularly since you are allowed to reuse some of the code from insert.

When you are done, submit the file


Implement method remove in class BST in file, without using recursion. (You will get an automatic zero for this part if you use any form of recursion in your answer.)

This will be worth more marks because it is slightly more difficult (but not much more). It requires you to take the time to really understand what the recursive version of remove is doing, to be able to do the same thing without recursion.

When you are done, submit the file


It is very easy to find solutions to this exercise online — even if you are just looking for "general explanations," you are likely to run into descriptions of programs. (Of course, you already have a program and a general explanation of how to carry out those two operations, from lectures!)

Please keep in mind all of the trouble that some students got into because of Exercise 4. And remember that we can search for code online just as well as you can, and we will check everyone's submissions against what we find...

But more importantly (much more importantly), please remember that the main purpose of this exercise (like all other exercises) is to help you get the practice you need to get better, and the confidence that your answer is correct, from doing it yourself. Also, we are here to help you! We (myself and the TAs) are available to answer your questions and help you solve the problem on your own. Please make use of the resources at your disposal (office hours, course forum, labs) and don't throw away this opportunity to learn.