Algorithms and OOD (CSC 207 2014F) : Labs

# Laboratory: Binary Search Trees

Summary: We explore the design and implementation of binary search trees, focusing on the ways in which we navigate and iterate such trees.

## Preliminaries

As you may recall, a binary search tree is a linked data structure designed with the “divide and conquer” strategy. The tree consists of nodes, each of which contains a key, a value, and links to two other trees. (Those links may also lead to null.) We speed up searching by ensuring that all the “smaller” keys fall in the left subtree and that all of the “larger” keys fall in the right subtree.

In such a tree, it should be easy to find a key.

search(key,node)
If the node is null, the key is not there
Give up // Return a special value, throw an exception, ...
Otherwise
Compare key to the node's key
If key equals the node's key, we've found it
Return the value
Otherwise, if key precedes the node's key,
Recurse on the left subtree
Otherwise, key follows the node's key
Recurse on the right subtree

## Preparation

Fork and clone the repository at https://github.com/Grinnell-CSC207/bst.

Sketch the tree that you expect to create by adding the following key/value pairs (in that order).

• e: elephant
• c: chinchilla
• b: baboon
• d: dingo
• a: aardvark
• g: gibbon
• f: flying squirrel
• h: hippo

## Exercises

### Exercise 1: Checking Trees

Our `BST.java` class includes a method, `dump`, that prints a tree using a simple format. In particular, given a node, we print

• the key/value pair for the node,
• the left subtree, indented by four spaces, and
• the right subtree, indented by four spaces.

Null subtrees are represented as `<>`.

a. Read through the code of `BSTExpt.java`. You will note that it uses the same sequence of operations as given above.

b. Run `BSTExpt` and compare the trees it gives to the trees you predicted.

c. Read the definitions of `set` and `insert` to understand how we build binary search trees.

### Exercise 2: Exploring Repetition

In some of our previous work, we've seen some errors when we reuse a key or value. So let's consider such situations.

a. Given your reading of `set` and `insert`, what do you expect to have happen if we call `set` with a key that we've used before?

b. What do you expect to have happen if we call `set` with a value that we've used before?

c. Check your answers experimentally. (You'll see two lines in `BSTExpt.java` that you can uncomment as a starting point.)

### Exercise 3: Printing Trees

a. Suppose you had to implement `dump`. Sketch the algorithm you would use. Note that each node in the tree contains a key, a value, and links to two subtrees called `smaller` and `larger`.

b. Compare your answer to our implementation of `dump`.

### Exercise 4: Similar Trees

Does the order in which we add elements to the tree matter?

a. Suppose we add elements to the tree in alphabetical order. What do you expect the tree to look like?

b. Update `BSTExpt` so that the elements get added to the tree in alphabetical order and see if the results are similar to what you predicted.

c. As you may have noted, when we add the elements in alphabetical order, we get a fairly unbalanced tree. Spend no more than five minutes considering how you might keep the tree more balanced. Do not attempt to implement your idea, but be prepared to discuss the idea.

d. Rearrange the lines that add elements so that they build some other tree. (It doesn't matter which; we just want something a bit more balanced.)

### Exercise 5: Implementing `get`

If you've looked at the `BST.java`, you'll note that some important methods are left unimplemented. One such method is `get`. Implement that method and add some experiments that help verify that your implementation is correct.

Note: You may find it easier to implement `get` with a helper method, similar to the one we used as a helper to `insert`.

### Exercise 6: Iterating Trees

We make it a habit to implement iterators for every collection we create. And so we should implement an iterator for our BST. In fact, we'll implement two, one for the keys and one for the values. Of course, their implementations are likely to be similar.

a. Sketch a strategy for implementing an iterator over binary search trees. Think about what data you will need to store and how you will implement the `next` and `hasNext` methods.

b. Compare your answer to the implementation in `BST.java`.

c. Suppose we create an iterator for the keys in the tree. In what order do you expect to see the values?

```for (String key : dict.keys())
{
pen.print(key + " ");
} // for each key
pen.println();
```

## For Those with Extra Time

If you find that you have extra time, you may want to attempt one or more of the following. (You can do them in any order.)

### Extra 1: Rethinking `get`

Some people find it natural to implement `get` recursively. Others find it natural to implement `get` iteratively. (I will admit that I fall in the first category.)

a. If you implemented `get` recursively, implement it iteratively. If you implemented `get` iteratively, implement it recursively.

b. Which do you prefer, and why?

### Extra 2: Implement `containsKey`

You'll note that we have not implemented `containsKey`. Implement that method without significantly duplicating code. (In order to avoid significantly duplicating code, you may need to generalize your code that implements `get` so that both `containsKey` and `get` can use the same core code.)

### Extra 3: Alternate Iterators

Right now, the iterators for our binary search tree iterate in the same order that we print the tree. But what if we want a different order? Say, suppose we want the root, then all the values that are one away from the root (the children), then all the values that are two away from the root (the grandchildren), then all the values that are three away from the root (the great-grandchildren), and so on and so forth.

Update the iterators to provide the values in that order.