CSC148H lab -- week 11

Here are the instructions for the week 11 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 search trees (BSTs).

Exercise 1: Putting data into a tree and fixing a bug

When it's your first turn as driver, begin by making a new folder "lab11". In lab11, save the files that we've provided for you: BST.java and Driver.java. In this lab, you will be modifying BST.java by adding new BST methods, and also modifying Driver.java to call the new methods.

1. Read the code for class BST, which is similar to the binary-tree class you used in week 9 except that a BST is now treated as a complete object with the root as a private instance variable. (In week 9, the binary tree's root was accessed directly by methods working with the tree. Both approaches make sense.)
2. Read the Driver class too. For a change, we're not making you write your own data-input loop.
3. Compile Driver.java. This will cause BST.java to be compiled too. Run the program with some sample data. It should run, but you'll find there's something wrong.
4. Fix the bug, which is in BST.java. It's not huge, but like all bugs might be a little tricky to find.

Exercise 2: Print the smallest item in the tree

Add a method smallest() to the BST class. It should return the smallest integer in the tree, or throw a NoSuchElementException if the integer isn't found. In Driver, you will need to catch the exception and print a sensible message.

NoSuchElementException is a part of the standard Java API, and is in java.util. It is a child of RuntimeException, so you won't need to put a "throws" clause in the header of your smallest() method.

Hint: you'll need a helper method. When a tree is represented as an object, very often the public methods (which won't have the root as a parameter) need to call private static helpers that take the root as a parameter.

Exercise 3: Print the smallest leaf in the tree

Now write smallestLeaf(), which is like smallest() but finds the smallest value stored in a leaf.

First, make sure you understand the difference between the smallest value anywhere in the tree and the smallest value in a leaf, by drawing a tree where the two are not the same -- that is, there is a value in a non-leaf that is smaller than any value in a leaf.

Again, throw a NoSuchElementException if the tree is empty.

Exercise 4: Print the depth of a value in the tree

The depth of a node in a tree is the number of steps downward you have to take to get from the root to the node. Thus, the root itself is at depth 0.

Write depth(int data), returning the depth in the BST of the node containing the value data, or -1 if data is not in the tree. In Driver, write a loop so that after the tree has been set up, the user can find the depth of various values in the tree.