# Homework 5: BSTs and Sorting

The goal of this assignment is to practice working with the binary search tree structure and with sorting algorithms. There is also an SRC Response to be completed, which relates to the Web Scraping Project out now. This should be handed in separately on Gradescope. Look towards the bottom of the handout for more information on the SRC Response!

## Setup and Handin

### Setup

In order to setup **homework5**, create a new project in PyCharm. Copy the
BST starter code below into a file named `bst.py`

. You should also create a file names `sorting.py`

, which is outlined later in the handout.

### Handin

Hand in the following files to Gradescope when submitting the assignment:

`bst.py`

`test_bst.py`

`sorting.py`

`test_sorting.py`

`README.txt`

Remember to include a README.txt when submitting your assignment!

## Staff Assistance

Your friendly TAs and Professor are here to help with this assignment! You can find our hours schedule here.

## The Assignment

### Binary Search Trees

Here is a lightly cleaned up version of the Binary Search Tree implementation we
ended up with in class, which you should copy to a file called `bst.py`

:

```
class BSTNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def contains_at(self, node: BSTNode, data) -> bool:
if not node:
return False
if node.data == data:
return True
if data < node.data:
return self.contains_at(node.left, data)
else:
return self.contains_at(node.right, data)
def contains(self, data) -> bool:
return self.contains_at(self.root, data)
def count_at(self, node) -> int:
if not node:
return 0
return 1 + self.count_at(node.left) + self.count_at(node.right)
def count(self) -> int:
return self.count_at(self.root)
def add_to(self, node: BSTNode, data):
if node.data == data:
return
if data < node.data:
if node.left:
self.add_to(node.left, data)
else:
node.left = BSTNode(data)
else:
if node.right:
self.add_to(node.right, data)
else:
node.right = BSTNode(data)
def add(self, data):
if not self.root:
self.root = BSTNode(data)
else:
self.add_to(self.root, data)
```

Your task is to modify this binary search tree so that at each node it stores a
*value* in addition to a *key*. To do this, you will need to:

- Replace the
`data`

field on the`BSTNode`

class with two fields:`key`

and`value`

- Modify the
`contains`

and`contains_at`

method to search the tree using this new`key`

field instead of the`data`

field - Add a
`lookup`

method to the`BST`

class; it should take a key and return the corresponding value if it is present in the tree; otherwise, it should raise a`KeyError`

. Hint: this method’s implementation will be*very*similar to`contains`

, and should use a recursive helper method similar to`contains_at`

. - Modify the
`add_to`

method to take a key and a value (instead of the`data`

argument). It should use the`key`

argument to determine where to add a node. If a node with that key is already in the tree, it should instead replace its value.

You should not need to modify `count`

.

You should write good tests for the `contains`

, `count`

, `lookup`

, and `add`

methods in `test_bst.py`

. You do not need to include tests for any recursive
helper methods.

### Insertion Sort

In `sorting.py`

, write a function called `insertion_sorted`

that takes in a list
and returns a sorted list. Your function should use the insertion sort algorithm:

- Create a new list for the result of your function
- Loop over the elements of the input list
- For each element, put it in the right place in the result list
- Return the sorted result list

You can use the `insert`

method on lists. The insert method inserts an item into
a list at a given index; for example:

```
>>> lst = ["c"]
>>> lst.insert(0, "a")
>>> lst
["a", "c"]
>>> lst.insert(1, "b")
>>> lst
["a", "b", "c"]
>>> lst.insert(3, "d")
>>> lst
["a", "b", "c", "d"]
```

While your function implements the same algorithm as our insertion sort function from class, its implementation will look quite different: it’s building a new list rather than modifying its argument. For your reference, here is the insertion sort function we ended up with in class:

```
def insertion_sort(lst: list):
"""
Sort a list in place using insertion sort
"""
index = 1
while index < len(lst):
insertion_index = index
while insertion_index > 0 and lst[insertion_index] < lst[insertion_index - 1]:
element = lst[insertion_index]
lst[insertion_index] = lst[insertion_index - 1]
lst[insertion_index - 1] = element
insertion_index = insertion_index - 1
index = index + 1
```

You should write tests for your sorting function in `test_sorting.py`

.

## README

In your `README.txt`

, please include answers to the following questions:

- Did you discuss this assignment with any other students? Please list their cs logins.
- How many late days are you using on this assignment?

## SRC Response

Look over the **SRC Response Handout** linked here. This SRC Response asks you to reflect on the social implications of your web scraping project. Unlike the previous SRC Responses, there will **NOT** be a peer review for this response.