CSC 148 H1, Winter 2013

Exercise 5

Due: before noon on Friday 8 March 2013

Pre-marking: first run begins at noon on Wed. 6 Mar.; second run begins at noon on Thu. 7 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!

Important general advice

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, do some searching on Google and ask on the course forum or during office hours to make sure you find out. Keep in mind that the lab for this week will cover related material, so taking the time to understand the lab (and ask questions of other students and of your TA) should provide good preparation for this exercise!


Background

Just like last week, both parts of this exercise concern binary trees that are not binary search trees.

You have to write two methods — one each in Part A and Part B — to add to the following node class (available for download from the course website so that you don't have to copy-and-paste it from this handout).

class BTNode(object):
    """A node in a binary tree."""

    def __init__(self, item, left=None, right=None):
        """(BTNode, object, BTNode, BTNode) -> NoneType
        Initialize this node to store item and have children left and right,
        as well as depth 0.
        """
        self.item = item
        self.left = left
        self.right = right
        self.depth = 0  # the depth of this node in a tree

    def __str__(self):
        """(BTNode) -> str
        Return a "sideways" representation of the subtree rooted at this node,
        with right subtrees above parents above left subtrees and each node on
        its own line, preceded by as many TAB characters as the node's depth.
        """
        # If there is a right subtree, add an extra TAB character in front of
        # every node in its string representation, with an extra newline at the
        # end (ready to be concatenated with self.item).
        if self.right:
            str_right = "\t" + str(self.right).replace("\n", "\n\t") + "\n"
        else:
            str_right = ""
        # The string representation of self.item: if item is a string, use
        # repr(item) so that quotes are included and special characters are
        # treated correctly -- just like in a list; else use str(item).
        if isinstance(self.item, str):
            str_item = repr(self.item)
        else:
            str_item = str(self.item)
        # If there is a left subtree, add an extra TAB character in front of
        # every node in its string representation, with an extra newline at the
        # beginning (ready to be concatenated with self.item).
        if self.left:
            str_left = "\n\t" + str(self.left).replace("\n", "\n\t")
        else:
            str_left = ""
        # Put the right subtree above the root above the left subtree.
        return str_right + str_item + str_left

Part A

Copy the code for class BTNode into a new file named "e5a.py" and add the following method to the class — this includes writing the body of the method! You must not change the constructor for class BTNode, but you are allowed to add additional helper methods if you think they are necessary. However, note that there is a way to do this with no helper in about half a dozen lines: if your code is much longer, there is a chance that you are missing something. Think about it carefully to see if you can simplify.

    def set_depth(self, depth):
        """(BTNode, int) -> NoneType
        Set the .depth attribute of every node in the subtree rooted at this
        node, starting with this node at depth 'depth'.
        """

Hint: First, draw a few simple trees and make sure that you understand what the correct result should be. Then, remember to think recursively!


Part B

Copy the code for class BTNode into a new file named "e5b.py" and add the following method to the class — this includes writing the body of the method! You must not change the constructor for class BTNode, but you are allowed to add additional helper methods if you think they are necessary. However, note that there is a way to do this with no helper in about a dozen lines: if your code is much longer, there is a chance that you are missing something. Think about it carefully to see if you can simplify.

    def leaves_and_internals(self):
        """(BTNode) -> ([object], [object])
        Return a pair of lists: (list of all the items stored in the leaves of
        the subtree rooted at this node, list of all the items stored in the
        internal nodes of the subtree rooted at this node).
        """

Hint: First, draw a few simple trees and make sure that you understand what the correct output should be. Then, remember to think recursively!