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`

## 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)

if node.data == data:
return
if data < node.data:
if node.left:
else:
node.left = BSTNode(data)
else:
if node.right:
else:
node.right = BSTNode(data)

if not self.root:
self.root = BSTNode(data)
else:

``````

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`.

In your `README.txt`, please include answers to the following questions: