**Homework 11: BSTs, File I/O, Errors** **Reed CSCI 121 Spring 2026**   *As a **BONUS** exercise complete these by 9am on 5/12.* There are three kinds of problems below related to the last three topics of the course. These are extra and are provided so that you can exercise this additional material. You'll want to work to complete these if you intend to continue on in computer science. Even if that isn't your plan, working on them will help you round out your understanding of the course material. (##) BSTs For the first problems we ask you to add methods to the class definition of a binary search tree. We've provided [**starting source code**](BSTree.py) for that class. It contains a `BSTNode` class that describes the nodes that make up the structure of a binary search tree. Each such node `n` has an `n.key` for its data item, and also an `n.left` and an `n.right` that each might link to other nodes in the tree. Or they each might have the value `None`. The file also contains a definition of a `BSTree` class that is a binary search tree implementation of an *ordered set* as described in lecture. A binary search tree object `t` has a single attribute `t.root` that refers to the root node of the tree, an object of type `BSTnode`. You can `insert` and `delete` values into and from the tree's set. You can also check whether a tree `contains` a value. It organizes them by order so that searching happens quickly. In addition, we have *tree traversal* code for computing the `size` of the tree and producing a list of its items in order. Below gives an interaction that builds binary search trees. The first is just an empty tree. The second has a collection of integer values. ~~~none >>> t1 = BSTree() >>> t1.asList() [] >>> t2 = BSTree() >>> t2.insert(17) >>> t2.insert(31) >>> t2.insert(90) >>> t2.insert(5) >>> t2.insert(14) >>> t2.insert(89) >>> t2.asList() [5, 14, 17, 31, 89, 90] >>> t2.contains(14) True >>> t2.contains(13) False >>> 14 in t2 True >>> t2 <5, 14, 17, 31, 89, 90> ~~~ Note that we've added `__`-named "special methods", like we did with linked lists, so that we can use a lot of standard syntax to work with our binary search trees. --- (##) `[Hw11 Ex1]` search path The search path for a key stored in a binary search tree is the sequence of "hops" performed by following `left` and `right` links down the tree in a search for that key using the get method. Write a method `searchPath` for the class `BSTree`. It should take a key that may or may not be stored in the binary search tree. If that key is stored in the tree, it should give a string that describes the search path taken to find that key. This string should be a sequence of `'L'` and `'R'` characters. If the key is not stored in the tree it should return the same kind of string. In that case, it describes where that key's node would be placed were it to be inserted into the tree. For example: ~~~ none >>> t = BSTree() >>> t.insert(5) >>> t.insert(0) >>> t.insert(1) >>> t.insert(7) >>> t.insert(2) >>> t.insert(13) >>> t.searchPath(2) 'LRR' >>> t.searchPath(7) 'R' >>> t.searchPath(5) '' >>> t.searchPath(4) 'LRRR' ~~~ (##) `[Hw11 Ex2]` height The height of a binary search tree is the length of the longest search path among all the keys stored in the tree. (See the searchPath problem for a description of a key's search path.) Note that a tree with only one key has a height of 0. Note also that the height of an empty binary search tree is defined as -1. Write a method `height` for the class `BSTree`. It should compute and return the height of its tree. For example: ~~~ none >>> t = BSTree() >>> t.height() -1 >>> t.insert(5) >>> t.height() 0 >>> t.insert(0) >>> t.insert(1) >>> t.insert(7) >>> t.insert(2) >>> t.insert(13) >>> t.height() 3 ~~~ **Hint:** its best to think of this recursively. The height of any empty subtree is -1. The height of any non-empty subtree is 1 more than the larger of the height of its left and right subtrees. Write a recursive helper function that takes a `BSTnode` and returns the height of its subtree. (#) File I/O The exercise below asks you to write a function that reads an input file and writes an output file. You might refer to the example code given in the lecture slides to help you complete it. You'll want to read all the lines from a text file, process their strings, make a bunch of new strings, then write them out to a file. The file is meant to represent something similar to a spreadsheet, basically a table of values. (##) `[Hw11 Ex3]` transpose Consider the contents of a text file that contains a table of integers. That table consists of a certain number of rows and columns. The first line of the file contains two numbers, separated by a space, describing the number of rows and the number of columns. The remaining lines of the file each contain one row of that table, with its columns of numbers separated by commas. For example, consider the following 3 x 5 table: | 3 | 1 | 10 | 0 | 17 | |:--:|:--:|:--:|:-:|:--:| | -1 | 8 | 33 | 2 | -5 | | 9 | 12 | 6 | 0 | 0 | (Please ignore the shading. It is a quirk of this web page's formatting.) This would be represented as a text file with the contents ~~~ 3 5 3,1,10,0,17 -1,8,33,2,-5 9,12,6,0,0 ~~~ If read in as a single string on Mac or Linux systems, it would be ~~~ "3 5\n3,1,10,0,17\n-1,8,33,2,-5\n9,12,6,0,0\n" ~~~ (On Windows systems the lines would end with the two special characters `\r\n` instead.) Write a function `transpose` that takes two strings as parameters. The first should be the name of a file that contains such a table, one that the function will read. The second should be the name of a file that it will create and then write into. It should output the table that results from "flipping" the table over its diagonal, so that the rows of the input table become the columns of the output table, and vice versa. For example, it should produce this output for the table above: ~~~ 5 3 3,-1,9 1,8,12 10,33,6 0,2,0 17,-5,0 ~~~ This corresponds to the table below: | 3 | -1| 9 | |:-:|:-:|:-:| | 1 | 8 | 12| | 10| 33| 6 | | 0 | 2 | 0 | | 17| -5| 0 | You can assume that the input table has at least one row and one column. **Hint**: I *strongly* recommend that you build a table to hold all the values after they've been read, and before the transpose has been written. This can be a list of all the rows, with each list being a list of all the values in that row. The example input table would be this list of lists: ~~~ python [[3, 1, 10, 0, 17], [-1, 8, 33, 2, -5], [9, 12, 6, 0, 0]] ~~~ **Note:** It's okay to use some of the built-in Python functions we've used in other labs for working with strings. For example, you might find `split` and `join` to be very useful here. Another useful one (that I haven't yet explicitly mentioned) is `rstrip`. These are each described below: * `s.split(c)`: this takes a string `s` and splits it into a list of strings when text in `s` is separated by character `c`. So, for example, `"abe bob dog".split(' ')` gives the list `["abe", "bob", "dog"]`. * `c.join(sl)`: this takes a list of strings `sl` and builds a single string using character `c` as their separator. So, for example, `','.join(["abe", "bob", "dog"])` gives `"abe,bob,dog"`. * `s.rstrip()`: gives a string with whitespace characters removed from the end of `s`, if there are any. So `"hello there \n".rstrip()` will be `"hello there"`. This is a platorm-independent way of removing the special line-ending characters on Mac, Linux, and Windows systems. (#) Exceptions Python has a feature that allows your program to track and react to errors that might arise during its execution. Your code can `try` and run some code and handle any *exceptions* that arise with `except` clauses. Here, for example, is a simple use of a "try except" block: ~~~ python success = False while not success: try: x = int(input("Enter an integer: ")) success = True except: print("That didn't work. Try again.") print("You entered "+str(x)+".") ~~~ If, say, the user enters a string that isn't an integer, then a `ValueError` exception would normally be raised, halting the program after `input` returns that string. Here, instead, the `except` code catches that error, prints the "Try again." message, and the loop repeats. ~~~ none Enter an integer: hello That didn't work. Try again. Enter an integer: 45.5 That didn't work. Try again. Enter an integer: 45 You entered 45. ~~~ Without the error handling, we'd normally see this with the `input`: ~~~ none Traceback (most recent call last): File "/Users/jimfix/example.py", line 4, in x = int(input("Enter an integer: ")) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ValueError: invalid literal for int() with base 10: 'hello' ~~~ (##) `[Hw11 Ex4]` function map Write a function `function_map` that takes a function (say, `f`) as a parameter and an integer (say, `n`) as a parameter. It should return a list of length `n` describing how that function behaves when given an integer from `0` to `n-1` as input. If it handles an integer input `i` with no errors, then list item `i` should contain `f(i)`. If instead `f(i)` leads to an error, the `i`-th item should be `None`. For example the function fed to `map_function` below divides by 0 when `x` is 2, but gives answers otherwise. ~~~ >>> function_map(lambda x: 10 // (x - 2), 5) [-5, -10, None, 10, 5] ~~~