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!
Don't forget to test your code style using pep8 -- see the handout for Exercise 2 for a refresher!
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 exercise, you will work on code for Binary Search Trees. Please review the lecture material on this topic before you start. In particular, read the code posted on the course website carefully.
Download the file "bst_iter.py
" from the course website and
make two separate copies of this file: one named "e4a.py
" and the
other named "e4b.py
". You will be adding code to these files.
__contains__
Implement method __contains__
in class BST
in
file e4a.py
, without using recursion. (You will
get an automatic zero for this part if you use any form of recursion in your
answer.)
Note that you are allowed to reuse some of the code from
insert
.
When you are done, submit the file e4a.py
.
max_node
Implement method max_node
in class BST
in file
e4b.py
, without using recursion. (You will get an
automatic zero for this part if you use any form of recursion in your answer.)
This method assumes it is called on a non-empty tree and returns the node with the maximum item.
When you are done, submit the file e4b.py
.