CSC 148 H1, Winter 2013

Exercise 4

Due: before noon on Friday 1 March 2013

Pre-marking: first run begins at noon on Wed. 27 Feb.; second run begins at noon on Thu. 28 Feb.

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

Both parts of this exercise concern binary trees that are not binary search trees. All the keys (that is, the data stored in the tree nodes) are expected to be integers. Even though the functions in both parts should work on some kinds of non-integer data, we will use only integers in testing.

You have to write two functions — one each in Part A and Part B. Both functions should assume that a tree is stored in a set of nodes defined by this class:

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

    def __init__(self, key, left=None, right=None):
        """Initialize this node with the given key, left child, and right child.
        """
        self.key = key
        self.left = left
        self.right = right

You should write a file "node.py" containing the code for class BTNode, but you do not need to submit node.py, because we will supply our own copy. (It is alright if you submit it, however; we will just ignore your file.)

The files you submit for marking must include the line:
  from node import BTNode


Part A

Consider re-constructing a binary tree from its pre-order and in-order traversals. For example, if the lists of keys resulting from the traversals are [10, 6, 8, 12, 11, 15] (pre-order) and [8, 6, 12, 10, 11, 15] (in-order), then we can see that:

Submit a file called "e4a.py" that defines a function make_tree(preorder, inorder). This function must return a BTNode containing the root of a binary tree whose pre-order and in-order traversal lists are given as arguments. If either preorder or inorder is empty, both of them must be empty and the function's return value must be None.

We promise not to use test cases containing two keys with the same value. Also, your function can assume that the parameters represent correct pre-order and in-order traversals of the same binary tree. We will not test your code with invalid parameters.

Our test programs will access your function by including the line:
  from e4a import make_tree

Hint: Think before you code! In particular, work through a number of small (and large) example by hand to figure out exactly how to solve the problem, before you attempt to write the function.


Part B

Submit a file called "e4b.py" that defines a function sum_to_deepest(root) that returns the sum of the keys from the root to the deepest leaf, in the tree rooted at root. If there are two deepest leaves, return the larger sum; if the root is None, return 0. In the tree used as an example in Part A, the sum would be 10 + 11 + 15 = 36.

In this problem, you will find it helps to define a helper function that returns both the depth of the deepest leaf and the sum along the path to that leaf.

Our test programs will access your function by including the line:
  from e4b import sum_to_deepest

Hint: Just like for Part A, work through a number of small (and large) example by hand to figure out exactly how to solve the problem, before you attempt to write the function.