CSC148H lab -- week 9

Here are the instructions for the week 9 CSC148H 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 "lab9". In lab9, save the files that we've provided for you: BTNode.java and Driver.java. In this lab, all the exercises involve modifying Driver.java -- usually by adding one or more functions and then making main() call the new functions -- so it's really more than just a "driver".

1. Read the code for class BTNode, which is similar to the node class for a typical linked list, except that there are two links instead of one.
2. Fix the body of the main() method in class Driver, following the directions given in the comments in main().
3. Compile the code and run it. You should be asked for a sequence of integers. These integers are put into a tree, which is then printed.
4. The output from our simple-minded print() method is a little hard to figure out. Look hard at it and draw a diagram showing the tree in a more conventional style, with the root at the top. Your tree won't look like a well-behaved tree, because it's unbalanced: the insert() method just puts everything into the rightmost place in the tree.

Exercise 2: Making the tree a nicer shape

After Exercise 1, we can create a tree, but it doesn't look much like a tree. 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 to in the left subtree of the root, and sometimes in the right subtree. In real applications, you usually have 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 throw dice at each level of the tree to decide whether to go left or right.

Modify the insert() method 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 Math.random(). The return value of Math.random() is a double value between 0 and 1, so there's a 50% chance it will be less than 1. You can make your program "flip a coin" like this:

if (Math.random() < 0.5) {
  ... you got "heads"
}
else {
  ... you got "tails"
}

Here's another hint: define a boolean variable "goingRight" and change it depending on the "coin flip" just suggested. Here's how to change its value from false to true or from true to false:

goingRight = ! goingRight;

To summarize: at every level in the tree, pick a direction (left or right) randomly. If the link in that direction is null, 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 methods: sum(root) and largest(root) that find the sum of all the integers in a tree and the largest of all the integers in a tree. Print the results, of course.

Your methods should work even if the tree is empty (that is, if the root is null). You can't test that until after the next part, but it should be easy to manage.

(The sum of 0 integers is 0. Let's let the largest of a set of 0 integers be Integer.MIN_VALUE, even though you could probably start an argument about that.)

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() so that it works if the root is null when it's called. This is harder than you'd think, because if the root is null, then it needs to be modified. Since a method can't change its parameters (at any rate, any changes can't be visible to the caller), insert() will have to be modified so that it returns the root, possibly changed. Of course, that will also change the way insert() is used in the rest of the program.

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

Try your sum() and largest() methods 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 branches that you have to follow to get from the root to the farthest-down leaf. Thus, the height of a tree with one non-null node (the root) is 0. We'll define the height of an empty tree (with no nodes at all) to be 0 also.