Lab 10 (Mar. 26/27)

This document contains the instructions for lab number 10 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 work with the list representation for complete binary trees.

Getting started

Agree on who will be student "`s1`" and who will be student "`s2`" for this lab.
For this part, student `s1` drives and student `s2` navigates.

• In a file named "`compbt.py`", write a class `CompleteBinaryTree` that uses a list to store its values, as described during last week's lectures.
• Your constructor should take an optional list parameter to initialize the tree — in your constructor, use slicing to make a copy of the list argument. Then, discuss the following question with your partner (and other students and your TA, as needed): Why is it a good idea to make a copy of the list argument with slicing (writing code like: "`self.something = parameter[:]`" instead of "`self.something = parameter`")?
• Write a comment in your constructor to very briefly explain the answer to this question.
• Write three helper methods in class `CompleteBinaryTree`:
• `parent(self, i)`: return the index of the parent of the node at index `i` (or −1 if index `i` does not have a parent).
• `left(self, i)`: return the index of the left child of the node at index `i`.
• `right(self, i)`: return the index of the right child of the node at index `i`.
• Remember: draw lots of pictures!

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

Simple methods

For this part, student `s2` drives and student `s1` navigates.

Write code for the following methods in class `CompleteBinaryTree`.

• `preorder(self)`: return a list of the items stored in this tree, according to a pre-order traversal. Try to make your code as generic as possible. In other words, try to write your code so that it depends on the list representation as little as possible.
• `insert(self, item)`: insert `item` into this complete binary tree. There is no ordering required: `item` can be added anywhere. The only constraint is that the result must still be a complete binary tree. (Hint: this is actually very simple. Just make sure that you really understand what it means for a binary tree to be complete.)

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

More complicated but familiar...

For this part, student `s1` drives and student `s2` navigates.

Write code for the following method in class `CompleteBinaryTree`.

• `max_sum(self)`: return the largest sum of the items on a path from the root of this tree down to one of its leaves (the length of the path does not matter, only the value of the sum). Precondition: the items in this tree can all be added together and compared to each other.

When you are done, show your work to your TA. Then, please stick around to help other students in your lab section!