# 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!

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:

• The key at the root is 10, because that is how the pre-order traversal begins.
• There are three nodes in the left sub-tree, because there are three keys listed before 10 in the in-order traversal.
• Many other similar inferences can be made...

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.