**Homework 11: Binary Search Trees** **Reed CSCI 121 Spring 2025**   *complete the exercises by 9am on 4/22* For the first problems below, you are to enhance a class definition of a binary search tree. We've provided [starting source code](BSTree.py) where you'll add several methods. It contains the definition of 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` and an `n.value`, the two components that serve as an enrty in a dictionary data structure. It also has two references `n.left` and `n.right` that may link to other nodes in the tree or 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* dictionary 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`. Included in that class are definitions of methods for inserting and updating entries in the dictionary (`set`), looking up dictionary items' values by their key (`get`), computing the number of entries in the dictionary (`size`), finding the minimum-valued key (`minimumKey`), and gathering all the entries into a list (`asList`). Below gives an interaction that builds two dictionaries, each as a binary search tree. The first is just an empty tree. The second has entries whose keys are strings and whose associated values are integers. ~~~ >>> t1 = BSTree() >>> print(t1.asString()) {} >>> t2 = BSTree() >>> t2.set('carlos', 17) >>> t2.set('anna', 31) >>> t2.set('ben', 90) >>> t2.set('abe', 5) >>> t2.set('angel', 14) >>> t2.set('davide', 89) >>> print(t2.asString()) {'abe': 5, 'angel': 14, 'anna': 31, 'ben': 90, 'carlos': 17, 'david': 89} >>> t2['angel'] = 74 >>> 'zuzu' in t2 False >>> t2['zuzu'] = 100 >>> 'zuzu' in t2 True >>> t2['zuzu'] 100 >>> t2 {'abe': 5, 'angel': 74, 'anna': 31, 'ben': 90, 'carlos': 17, 'david': 89, 'zuzu':100} ~~~ Note that we've added `__`-named "special methods", like we did with linked lists, so that we can use a lot of standard dictionary syntax to work with our binary search trees. Because binary search trees provide an ordered dictionary, it easy to extract the entries from the tree in order of their keys. In this example's case, since the keys are strings, they are kept in *lexicographic* order. (This is just the order that words are sorted in a dictionary.) In most of the examples and test code for the exercises below, we will use integers as keys instead. --- (##) `[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: ~~~ >>> t = BSTree() >>> t.set(5,'abe') >>> t.set(0,'bob') >>> t.set(1,'dog') >>> t.set(7,'cat') >>> t.set(2,'ali') >>> t.set(13,'boots') >>> t.searchPath(2) 'LRR' >>> t.searchPath(7) 'R' >>> t.searchPath(5) '' >>> t.searchPath(4) 'LRRR' ~~~ (##) `[Hw11 Ex2]` smallest ancestor A node's ancestors are all the nodes on the search path to that node, including the node itself. This means that a node is its own ancestor. The root node is the ancestor of all the nodes in the tree. Add a method `smallestAncestor` to the class `BSTree`. The method should take a key, and return the smallest key amongst the ancestors of its node in the tree. This may be the key itself. If the key does not exist in the tree, the method should return `None`. For example, in the tree shown below, calling `tree.smallestAncestor(1)` should return 1. Calling `tree.smallestAncestor(20)` should return 12.  (##) `[Hw11 Ex3]` 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: ~~~ >>> t = BSTree() >>> t.height() -1 >>> t.set(5,'abe') >>> t.height() 0 >>> t.set(0,'bob') >>> t.set(1,'dog') >>> t.set(7,'cat') >>> t.set(2,'ali') >>> t.set(13,'boots') >>> 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. (##) `[Hw11 Ex4]` second minumum key Add a method `secondMinimumKey` to the class `BSTree`. It should find the second smallest key in a binary search tree. The method should take no arguments and return the second smallest key, or `None` if the tree has fewer than two nodes.