# 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!

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.

## Background

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 "`bst_iter.py`" from the course website and make two separate copies of this file: one named "`e6a.py`" and the other named "`e6b.py`". You will be adding code to these files.

## `__contains__`

Implement method `__contains__` in class `BST` in file `e6a.py`, 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 `e6a.py`.

## `remove`

Implement method `remove` in class `BST` in file `e6b.py`, 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 `e6b.py`.

# DANGER! WARNING! DANGER! WARNING! DANGER!

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...