Lab 7 (Mar. 5/6)

This document contains the instructions for lab number 7 in CSC 148 H1. To earn your lab mark, you must actively participate in the lab.
We mark you in order to ensure a serious attempt at learning, NOT to make careful critical judgments on the results of your work.

General rules

We will use the same general rules as for the first lab (including pair programming). See the instructions at the beginning of Lab 1 to refresh your memory.

Overview

In this lab, you will explore different ways to write functions for binary search trees.

Binary Search Trees (BSTs)

Step 0: Getting started

• Agree on who will be student "s1" and who will be student "s2" for this lab.
• Read through the entire handout for this lab quickly, so that you have an idea what you will have to do.
• Download the files "BST.py", "BST_rec1.py", "BST_rec2.py", "BST_rec3.py", and "BST_iter.py" from the course website, and read through all of them quickly.

When you are done, get ready to begin pair programming.

Step 1: Direct recursion

(Student s1 drives and student s2 navigates.)

• Open "BST.py" and "BST_rec1.py" in Wing.
• Read through the code in BST_rec1.py carefully and run BST.py to see the results. Make sure you ask questions if there is anything in the code that you don't understand. Do this before you try to write any of your own code.
• Implement method count_less in class BST in file BST_rec1.py. For this part, you must do this by writing a separate helper method in class BST and calling the helper within count_less. You are not allowed to add any method to class _BSTNode for this part.
• When you are done, run BST.py again to verify your results.
• Before you move on, think about the following questions. Do you understand what you just did? Can you describe how your code works and explain why it does the right thing? Or did you manage to get working code by "trial-and-error", without really understanding how it works?
It's OK if you don't fully understand how your code works for now, but keep in mind that you must ask questions (of your partner, of other students, of your TA) to ensure that you do understand by the end of your lab.

When you are done, show your work to your TA and switch roles.

Step 2: Indirect recursion

(Student s2 drives and student s1 navigates.)

• Open "BST_rec2.py" in Wing and change BST.py so that it imports from BST_rec2.py (near the top).
• Read through the code in BST_rec2.py carefully and run BST.py to see the results. Make sure you ask questions if there is anything in the code that you don't understand. Do this before you try to write any of your own code.
• Implement method count_less in class BST in file BST_rec2.py. For this part, you must do this by writing a helper method in class _BSTNode and calling the helper within count_less. You are not allowed to add any method to class BST for this part.
• When you are done, run BST.py to verify your results.
• Before you move on, think about the following questions. Do you understand what you just did? Can you describe how your code works and explain why it does the right thing? Or did you manage to get working code by "trial-and-error", without really understanding how it works?
It's OK if you don't fully understand how your code works for now, but keep in mind that you must ask questions (of your partner, of other students, of your TA) to ensure that you do understand by the end of your lab.

When you are done, show your work to your TA and switch roles.

Step 3: Recursive objects

(Student s1 drives and student s2 navigates.)

• Open "BST_rec3.py" in Wing and change BST.py so that it imports from BST_rec3.py (near the top).
• Read through the code in BST_rec3.py carefully and run BST.py to see the results. Make sure you ask questions if there is anything in the code that you don't understand. Do this before you try to write any of your own code.
• Implement method count_less in class BST in file BST_rec3.py. For this part, you must do this by writing a helper method in classes _BSTNode and _BSTNone and calling the helper within count_less. You are not allowed to add any method to class BST for this part.
• When you are done, run BST.py to verify your results.
• Before you move on, think about the following questions. Do you understand what you just did? Can you describe how your code works and explain why it does the right thing? Or did you manage to get working code by "trial-and-error", without really understanding how it works?
It's OK if you don't fully understand how your code works for now, but keep in mind that you must ask questions (of your partner, of other students, of your TA) to ensure that you do understand by the end of your lab.

When you are done, show your work to your TA and switch roles.

Step 4: Iteratively

(Student s2 drives and student s1 navigates.)

• Take the time to review your code from the previous three parts. Compare what you have done with the way that methods __str__ and insert were implemented, and discuss the following topics with your partner.
• Now is the time to ask any last question you have, to make sure that you fully understand how your code works.
• Once you understand all your code, and it all works, think about this: are there ways that you could simplify? (For example, perhaps you have extra bases cases that are not necessary because your general case already does the right thing).
• Discuss which recursive technique you find easiest to implement. Which one gives the simplest code at the end?
• Remember that one important goal of programming is to make your programs as easy to understand as possible: both for yourself, and for other readers of your code. So it is always a good use of your time to review code after you have written it, in order to clean it up: simplify where you can, remove redundancies, etc.
• Warning! The rest of this lab is challenging. It's OK if you don't finish the rest, but you should definitely think about it and get as far into it as you can. It is provided to make you realize that recursion is not your "enemy", but rather a very useful technique that can save you a lot of trouble — this is why it is so important for you to learn it!
• Open "BST_iter.py" in Wing and change BST.py so that it imports from BST_iter.py (near the top).
• Read through the code in BST_iter.py carefully and run BST.py to see the results. Make sure you ask questions if there is anything in the code that you don't understand. Do this before you try to write any of your own code.
• Implement method count_less in class BST in file BST_iter.py. For this part, you must do this without any form of recursion! But you are allowed to use a separate data structure to manage information... (Hint: think about the way that Python keeps track of information about recursive function calls.)
• When you are done, run BST.py to verify your results.

If you manage to get this done, show your work to your TA. Then, please stick around to help other students in your lab section!