Homework 3: Trees and Objects

The goals of this assignment are:

  • To get practice implementing methods on classes
  • To get practice designing and developing programs on trees

Due date

  • HW3 is due on Thursday, October 15th at 9pm EST.

Setup and Handin


In order to setup hw3, make a new PyCharm Project and name it hw3. For testing, make sure you install pytest in the new PyCharm Project. The functions you need to complete will be outlined later, but for now make sure you create the four following files:

  • tree.py
  • tree_test.py
  • messagecenter.py
  • messagecenter_test.py

Make sure you add the the stencil code for tree.py, which can be copied from here. In addition, make sure you add the stencil code for messagecenter.py, which can be copied from here.

For tree.py you will be working with HTMLTrees, so you will need to create an additional file named htmltree.py and add this code to it. This contains the structure of the HTMLTree, which is imported into tree.py.


You may submit as many times as you want. Only your latest submission will be graded. This means that if you submit after the deadline, you will be using a late day – so do NOT submit after the deadline unless you plan on using late days.

The README template can be found here. Please follow the design and clarity guide–part of your grade will be for code style and clarity. After completing the homework, you will submit:

  • README.txt
  • tree.py
  • tree_test.py
  • messagecenter.py
  • messagecenter_test.py

Because all we need are the files, you do not need to submit the whole project folder. As long as the file you create has the same name as what needs to be submitted, you’re good to go!

If you are using late days, make sure to make a note of that in your README. Remember, you may only use a maximum of 3 late days per assignment. If the assignment is late (and you do NOT have anymore late days) no credit will be given.

Please don’t put your name anywhere in any of the handin files–we grade assigments anonymously!

You can follow this step-by-step guide for submitting assignments through Gradescope here.

Helpful Things


Staff Assistance

Your friendly TAs and Professor are here to help with this assignment! You can find our schedule for office hours here.

The Assignment

Part 1: For the love of Newton

On our amazing race for cs112 we make a stop by Woolsthorpe Manor, the famous location where Isaac Newton reportedly came up with the law of gravity. While touring the estate, the guide informs us that our next clue is at the top of the tree! We want to reach the top but we don’t know how high our ladder needs to be. Doug points out that we can model the famous tree with an html tree. We need your help so we can understand more about the tree and get to our next clue!

We’d like you to write the following functions on HTMLTrees in the tree.py file.


tree_height computes the maximum distance from the root to any leaf. This function should take an HTMLTree and return an integer. The height of a tree with no children is 1; the height of a tree with children is the maximum height of any of its children plus 1.


has_strong_grandchildren should return True if any of the grandchildren of the node at the root of the tree (i.e., children of its children) have the "strong" tag. Note that it doesn’t matter whether the root of the tree or any of its children are strong, we only care about the grandchildren. has_strong_grandchildren should take an HTMLTree and return a boolean.

Part 2: Getting the message

Now that we have our tree, it’s time to spread our message with everyone in the class. Just as we begin to text every one the clue, our messaging app loses international coverage! How are we ever going to tell everyone about our next leg of the journey? It’s up to you to build a messaging class that we can use to share this info and keep our race going.

You should write code for this part in messagecenter.py. Here’s some starter code:

class Message:
    def __init__(self, from_user: str, to_user: str, contents: str):
        self.from_user = from_user
        self.to_user = to
        self.contents = contents
        self.read = False

    def mark_read(self):
        self.read = True

For this part, you’ll write some code to implement a messaging application–think WhatsApp. Your application will track messages (as a list of Message objects, defined above) and groups, which are sets of users. Users can send messages either to other users or to a group; sending a message to a group results in it being sent to every user in the group. Your messaging applicaiton will be implemented as a class called MessageCenter.

Your MessageCenter class should implement the methods below. Remember that all of your methods need to take self as their first argument! We list the other arguments below.


The __init__ method doesn’t need to take any arguments besides self. It should add messages and groups fields to the object; these should be an empty list responsible for keeping track of the messages and an empty hashtable in charge of the different groups present in the message center, respectively.


This method should take (in addition to self) the name of a group (a string) and the name of a user (also a string). It should add a group with the given name if it doesn’t exist, and then add the named user to the group if it’s not already in the group.


add_direct_message should take (in addition to self) two users and a message body. It should create a message with the given users and body and store it in the messages list.


add_group_message should take (in addition to self) a user, a group, and a message body. If the given group exists, it should add messages with the given body from the given user to every member of the group.


next_message should take (in addition to self) a user and return the first unread message in the messages list addressed to that user. Before returning the message, it should mark the message as read using the mark_read method.


message_history should take (in addition to self) two users and return all of the messages (read or unread) between those two users–messages from the first user to the second user and vice versa.