---
tags: Homeworks
---
# CS15 Homework 2: Recursion and Trees

Do this assignment in Java, not Python

## Binary Search Trees

Imagine that you had a set of numbers such as

and you wanted to organize it in a way that showed the ordering relationship among the numbers. You could make a sorted list, but checking whether a specific number is in a list can take time linear in the size of the list.


A binary search tree (BST) is a binary tree (meaning a tree with at most two branches from each node/point) in which every node has the following property:

Every element in the left subtree is smaller than
the element at the root, every element in the right
subtree is larger than the element at the root, and
both the left and right subtrees are BSTs.

(this statement assumes no duplicates, but that is okay since we are modeling sets. If you want duplicates, change less-than to less-than-or-equal in the definition). 

Here is one example BST on our sample set:

10
/ \
4 12
/ \
2 7
/ \ / \
1 3 6 8
/
5

:::info
**Practice (not for turn in):** Draw two more BSTs on the same collection of numbers. Start with a different number at the top (called the *root*) and see what you come up with. Can you make distinctly different shapes?
:::

:::info
**Practice (not for turn in):** Which of the following are BSTs on the numbers from 1 through 5?

4 3 4 3
/ \ / \ / \ / \
5 3 2 5 2 5 1 5
/ \ / / / \ /
1 2 1 4 1 2 4
\
3

:::

### Classes for BSTs

We want to capture binary search trees using classes in Java (similar to how we used classes to capture lists in the lecture on Jan 29). 

**Task:** Create a collection of classes, abstract classes, and interfaces as needed to capture BSTs.

**Task:** Use your class hierarchy to create a specific BST on the numbers 1 through 5 (you pick which one, but have it be one that has at least some branching in it).

**Task:** Draw the memory contents for the example that you have created (we'll discuss this on Mon Feb 1).

### Searching in BSTs

Imagine you were given a BST representing a set of numbers, and were asked whether a specific number is in the set. How would the algorithm proceed?

- **If the tree is a leaf** (off the end of the tree with no data), return false
- **If the tree is not a leaf**
   - **if the number you're seeking is at the root**, return true
   - **If the number you are seeking is smaller than the number at the root**, search in the left subtree
   - **If the number you are seeking is larger than the number at the root**, search in the right subtree

:::info
**Practice (not for turn in):** Using the same tree we provided, work through a couple of example searches, some of numbers in the tree and some not in the tree.
:::


**Task:** Write a `hasElt` method on BSTs that takes a number and returns a boolean indicating whether the number is anywhere within the BST.

### Creating BSTs

How do we build-up a BST, however? For lists, we start with an empty list and add items. We need to do something similar with a BST. 

Assume you are given a BST and a number. You add an element to the BST by looking through the tree for the leaf where the number should be, then putting the number in that spot. For example, assume you wanted to insert the number 4 into the following tree:

8
/ \
5 9
/ \
3 7

We'd start at the root, and ask whether 4 is less than or greater than 8. Less than, so we should insert 4 on the left (so that we maintain the requirement on a BST). Now we compare 4 to 5. Less than, so we insert on the left. Now compare 4 to 3. Larger than, so we insert on the right. But the right is a leaf, so that is where we put the 4. Here's the resulting BST:

8
/ \
5 9
/ \
3 7
\
4

Notice that in this algorithm, new elements are always inserted at the leaves, not in the middle of the tree.  This disrupts the tree as little as possible, while still maintaining the BST requirement.

:::info
**Practice (not for turn in):** By hand, follow the above algorithm to create BSTs for each of the following setups on the same numbers:

- start with a leaf, then add `3, 1, 2, 4` in that order

- start with a leaf, then add `4, 3, 2, 1` in that order

- start with a leaf, then add `4, 2, 1, 3` in that order
:::

**Task:** Write an `addElt` method (our description explained the algorithm, which inserts at leaves). Don't forget to write test cases (and writing them first could *really* help you here, especially in the leaf case). 


## Time Efficiency of BST search

The appeal of BSTs compared to lists is that it seems searching and adding elements should be faster than on lists.

**Task:** Upload a PDF file with your answers to the following four questions (you are welcome to draw on paper, take a photo, and include that in your PDF for the drawing parts).

- Make an informal argument (in prose) for why these operations should be faster on BSTs than on lists.
- Now think through the argument through examples. Try to make three different BSTs for the same set of numbers (use the set we gave above) for which the running time would seem measurably different when searching for the same number. Show your examples (as pictures is fine -- whatever is easiest).
- How does this suggest you revise your informal argument?
- Write a formal recurrence relation for BST search and solve it. What running time do you get? (We will cover this in CS15 lecture on Monday 2/1.)

This is a topic we will return to in CS18. So if you feel like we may have left some threads dangling here, we did. We're just catching you up to CS17 for now.

## Files and Directories

Imagine that you wanted to write programs for managing directories and files on a computer. Each directory has a name and can contain both subdirectories and files. Each file has a name and size. 

Your goal is to design a class hierarchy to capture files and directory structures, then to write a series of methods that process directories (starting from a single "top-level" directory, like a Documents/My Documents folder).

As always, you should write tests for your methods.

**Task:** Create classes, abstract classes, and interfaces as needed to represented nested directories and files. You may assume that there is one top directory that all other files/directories lie within.

**Task:** Write a method `countFiles` on directories that returns a number indicating how many files are nested somewhere within that directory (no matter how deep).

**Task:** Write a method `anyEmptyDirs` on directories returns a boolean indicating whether any directory within the hierarchy is empty (has no files and no subdirectories).


## Reflection

In a block comment in the class with your tests, write a few sentences about what you’ve learned from these problems. Also mention any questions you have (if any) based on these exercises.