CSC148H lab -- week 5

Here are the instructions for the week 5 CSC148H/A48H lab. To earn your lab mark, you must actively participate in the lab. As always, you will work as a pair, taking turns being the driver and the navigator. The driver types, and the navigator watches for mistakes, thinking ahead. At the end of each exercise, show your TA what you've done, and then switch roles.

This week's exercises are on the topic of binary trees.

Exercise 1: Putting data into a tree

When it's your first turn as driver, begin by making a new folder "lab5". In lab5, save the files that we've provided for you: bt_node.py and driver.py. In this lab, all the exercises involve modifying driver.py -- usually by adding one or more functions and then calling the new functions -- so it's really more than just a "driver".

  1. Read the code for class BTNode, which is similar to the BinaryTree class seen in lecture.  Also examine the provided code in driver.py so that you know what helper functions are available to you. 
  2. Fix the body of the if __name__ == "__main__" in driver.py file, following the directions given in the comments.
  3. Run the code. You should be asked for a sequence of integers. These integers are put into a tree, which is then printed.

Tilt your head to the left and take a look at this: 

          4
      3
              9
          12
              7
It's a binary tree. 3 is the root, 4 is 3's right child, 12 is 3's left child, 9 is 12's right child, and 7 is 12's left child. It looks just like you'd expect a tree to look, provided your head is tilted. This is what the output of your program will look like.

Your tree won't look like a well-behaved tree, because it's unbalanced: the insert_node function just puts everything into the rightmost place in the tree.

Exercise 2: Making the tree a nicer shape

We can now create a tree, but it's not a good shape: it's just a line of nodes. In Exercise 2, we try to get the tree to spread out and use both left and right links instead of just right links. That is, when you're adding a new node to a tree, sometimes it should go in the left subtree of the root, and sometimes in the right subtree. As we'll see in the next lecture, there's usually a good reason for picking left or right, such as some idea of keeping the nodes in order, but here we'll just do it randomly. It's as if we flip a coin at each level of the tree to decide whether to go left or right.

Modify function insert so that it randomly chooses whether to go left or go right when moving down the tree. It still needs to keep going until it gets to a leaf, but we want it to follow an unpredictable path.

You can make a random choice between two alternatives by generating a random number with random.random. The return value of random.random() is a floating point value between 0 and 1, so there's a 50% chance it will be less than 0.5. You can make your program "flip a coin" like this: 

if random.random() < 0.5:
  ... you got "heads"
else:
  ... you got "tails"

To summarize: at every level in the tree, pick a direction (left or right) randomly. If the link in that direction is None, put the new node there; otherwise follow the link to the next level and repeat. You can do this recursively or iteratively.

Exercise 3: Simple tree operations

Write two functions: tree_sum(root) and tree_max(root) that respectively return the sum of all the integers in the tree rooted at root and the largest of all the integers in the tree rooted at root. Write code at the end of driver.py that calls those functions and prints the results.

The sum of 0 integers is, of course, 0. The maximum integer in an empty tree is None. tree_sum and tree_max should work even if the tree is empty (that is, if the root is None). You can't test that until after the next part, but it should be easy to manage.

Exercise 4: Letting the tree be empty

So far, we've assumed that the tree isn't empty for most of the critical operations, especially insert.

Modify insert_node so that it works if the root is None when it's called. This is harder than you'd think, because if the root is None, then it needs to be modified. Since a function can't change the values of variables in the function call (it can only change what those variables refer to), insert_node will have to be modified so that it returns the (possibly new) root. Of course, that will also change the way insert_node is used in the rest of the program.

Hint: you probably should use a helper function here. That can be avoided, but it does make the changes easier.

Try your tree_sum and tree_max functions on empty trees, as well as re-testing them on non-empty trees.

Exercise 5: How tall is the tree?

The height of a tree is the number of edges that you have to follow to get from the root to the farthest-down leaf. Thus, the height of a tree with one node (the root) is 0. The height of an empty tree (with no nodes at all) is defined to be -1.

Write a function height(root) that returns the height of the tree rooted at BTNode root. Try your function on some sample trees, including the empty case and the one-node case.