The main topics of this worksheet are:
The main references for these topics are:
The most useful files from the sample code repository are:
insert() method!)Suppose you have two nodes of binary trees, given as Node objects from binary.py. Let's call them x and y. You might ask how they are related to one another, if it all. In general, exactly one of the following statements will be true:
Write a function node_relationship(x,y) that takes two nodes and returns one of these strings:
"equal""ancestor""cousin""unrelated"according to which of the cases listed above describes the relationship between x and y.
(Note that the use of "cousin" to describe case (3) doesn't fit the genealogical analogy perfectly, as it would also include the case of siblings.)
Also, make test cases for your function that generate each of the possible answers.
You sould only use class Node from binary.py. You should NOT use bst.py at all.
bst.py¶The rest of the worksheet focuses on adding features to the module bst.py from lecture. To prepare for that, download these files and save them in a directory where you'll work on worksheet 8:
It will be hard to test your code if you don't have any search trees to test it with. To that end, I created a module treeutil.py (which you were asked to download above) that will generate random binary search trees on request. It can also give a random node of the tree, or a random pair of nodes.
Here are some quick examples of how to use it. When you add new features to bst.py, it is probably a good idea to test them out on some randomly generated trees, and to print both the tree and the results your code gives, so you can do a visual check for correctness.
import sys
sys.path.append('/home/ddumas/teaching/mcs275/public/samplecode/trees')
# Make and print a random tree with 5 nodes
import treeutil
import treevis
T = treeutil.random_bst(nodes=5)
treevis.treeprint(T)
# Make a random tree and select one of its nodes
import treeutil
import treevis
T,x = treeutil.random_bst_and_node(nodes=6)
treevis.treeprint(T)
print("I selected node:",x)
# Make a random tree and select two of its nodes
import treeutil
import treevis
# You can ask for two nodes that are always different (distinct=True)
# or you can allow the possibility that they will be equal (distinct=False)
T,x,y = treeutil.random_bst_and_node_pair(nodes=7,distinct=True)
treevis.treeprint(T)
print("I selected these two nodes:",x,y)
Add two new methods, minimum and maximum to the BST class for finding the node with the smallest or largest key (either in the whole tree, or in the subtree with a given node as its root). Use the method definitions and docstrings given below, which also give a more detailed specification for how these methods should work.
# These should go inside class `BST` in `bst.py`
def minimum(self,x=None):
"""In the subtree with root `x`, find and return a node with
the smallest key. If `x` is not specified, use `self.root`."""
def maximum(self,x=None):
"""In the subtree with root `x`, find and return a node with
the largest key. If `x` is not specified, use `self.root`."""
Add a method depth to the BST class that computes the depth of the tree (optionally starting at a certain node rather than the root).
# This should go inside class `BST` in `bst.py`
def depth(self,x=None):
"""Return the length (in number of edges) of the longest descending
path starting from node `x`. If `x` is not specified, use `self.root`"""
Suppose you are given a binary search tree T and a node x that has no children. If you change the key of x, the tree may or may not be a binary search tree.
Here's an example to illustrate this. Consider this BST:
<15>
<9> <29>
<5> <12>If x is the node with key 12, then changing the key to 13 still gives a binary search tree:
<15>
<9> <29>
<5> <13>But if we change the key to 6, the result is not a binary search tree; the right subtree of the node with key 9 contains keys smaller than 9:
!!NOT A BST!!
<15>
<9> <29>
<5> <6>And if we change the key to 18, the result is not a binary search tree. The left subtree of the root node contains a node with key larger than 15:
!!NOT A BST!!
<15>
<9> <29>
<5> <18>Now, if you look more closely at this example, you can convince yourself that the key 12 can be changed to any number in the closed interval $[9,15]$ while keeping the BST condition, but that anything outside of this range will result in a non-BST. This is called the interval of the node.
Add a method to BST that takes a node x with no children and returns a tuple (kmin,kmax) where kmin and kmax are the smallest and largest values (respectively) that the key of x could be changed to while keeping the BST condition. In some cases, there may be no lower or upper limit, in which case the value None should be returned for kmin, kmax, or both.
Use this method definition:
# This should go inside class `BST` in `bst.py`
def interval(self,x):
"""Given a node `x` with no children, return the minimum and maximum key values
that could be stored at `x` without violating the BST condition. The value None
is used to indicate that the range of allowable values has no upper or lower
bound."""
For example, in this tree:
<15>
<9> <29>
<5> <12>the intervals are:
<15> : None,None
<9> : None,15
<5> : None,9
<12> : 9,15
<29> : 15,NoneFinally, it may be helpful in this problem to recall that functions in Python can return multiple values, and if they do, the returned values are assembled into a tuple. That means the two statements below do the same thing:
return 1,2,3
return (1,2,3)
This is an extra activity to work on if you finish all the exercises above. This won't be included in the worksheet solutions.
Given a node x in a BST, you might want to know its successor, meaning the node whose key is larger than x but as small as possible given that condition. (We'll assume in this problem that all nodes in the tree have distinct keys).
It turns out that there is an efficient description of the successor as follows:
x has a right child, then the successor is the smallest key in the right subtree of xx does not have a right child, but has a successor, then the successor is an ancestor of x. If you visit these ancestors by traveling upward from x, then the first node you reach that is the left child of its parent is the successor.x has no right child, and if moving up from x to the root only ever visits nodes that are right children of their parents, then x is the maximum of the tree, so it has no successor.Write a method successor(self,x) of class BST that finds and returns the successor, or returns None if there is no successor.