The main topics of this worksheet are:
Project 3 will focus on tree-like data structures, so it is very important to get practice with this material!
These things might be helpful while working on the problems. Remember that for worksheets, we don't strictly limit what resources you can consult, so these are only suggestions.
Suppose you have two Node objects (or objects of a subclass of Node) as defined in trees.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:
"unrelated""equal""ancestor""cousin"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.
This solution makes use of a helper function ancestors, which lists all ancestors of a node x, starting from the node itself and ending with the root of the tree.
def ancestors(x):
"""
Given node, returns list containing its parent, its parent's parent, etc.
"""
L = [x]
while L[-1].parent != None: # While we can find a parent of the most recently-found parent
L.append(L[-1].parent) # Put parent into the list
return L
def node_relationship(x,y):
"""Returns string representing relation between nodes `x` and `y`."""
if x == y:
return "equal"
elif x in ancestors(y):
return "ancestor"
elif y in ancestors(x):
return "ancestor"
elif ancestors(y)[-1] == ancestors(x)[-1]: # If both share a root
return "cousins"
else:
return "unrelated"
trees.py¶The rest of the worksheet focuses on adding features to the module trees.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.
Open the full documentation of the module in a separate browser tab, and keep it open as you work:
The main things you'll be doing in such tests are:
treeutil functions to make trees to test your code ontreevis.treeprint to display trees for manual inspectionAdd two new methods, minimum and maximum to the BST class for finding the node with the smallest or largest key in the subtree that has this node as its root. Use these function definition lines and docstrings:
# These should go inside class `BST` in `trees.py`
def minimum(self):
"""
In the subtree that this node is the root of, find and
return the the smallest key.
"""
def maximum(self):
"""
In the subtree that this node is the root of, find and
return the the largest key.
"""
# These should go inside class `BST` in `trees.py`
def minimum(self):
"""
In the subtree that this node is the root of, find and
return the the smallest key.
"""
if self.left != None:
return self.left.minimum()
else:
return self.key
def maximum(self):
"""
In the subtree that this node is the root of, find and
return the the largest key.
"""
if self.right != None:
return self.right.maximum()
else:
return self.key
Add a method depth to the BST class that computes the depth of the tree. (That is, when you call A.depth() on a node A, you get the maximum number of descending edges that you can follow in the tree that has A as its root).
Note that both an empty BST and a 1-node BST are considered to have depth zero by this convention.
Use these function definition lines and docstrings:
# This should go inside class `BST` in `trees.py`
def depth(self):
"""
Return the length (in number of edges) of the longest descending
path starting from this node.
"""
# This should go inside class `BST` in `trees.py`
def depth(self):
"""
Return the length (in number of edges) of the longest descending
path starting from this node.
"""
# Base case: if there are no child Nodes
# then there are no further descending edges
if self.left == None and self.right == None:
return 0
# Otherwise, we can take one descending edge to
# a child, then take the longest descending path
# that continues from there. Thus the depth is
# 1 + depth of right subtree
# or
# 1 + depth of left subtree,
# whichever is LARGER.
if self.left == None:
left_depth = 0
else:
left_depth = self.left.depth() # recursive call
if self.right == None:
right_depth = 0
else:
right_depth = self.right.depth() # recursive call
return max(left_depth,right_depth) + 1
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:
❌THIS IS 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:
❌THIS IS 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 can be called whenever the node has no children, and which returns a tuple (kmin,kmax) where kmin and kmax are the smallest and largest values (respectively) that the key of that node 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. If called on a node that has children, it should raise an exception.
Use this method definition:
# This should go inside class `BST` in `trees.py`
def interval(self):
"""
If this node has no children, return the minimum and maximum key values that
could be given to this node without violating the BST condition. The value None
is used to indicate that the range of allowable values has no upper or lower
bound.
If the given node has children, raises ValueError.
"""
# This should go inside class `BST` in `trees.py`
def interval(self):
"""
If this node has no children, return the minimum and maximum key values that
could be given to this node without violating the BST condition. The value None
is used to indicate that the range of allowable values has no upper or lower
bound.
If the given node has children, raises ValueError.
"""
if self.left != None or self.right != None:
raise ValueError("Method `interval` may only be used on nodes with no children")
# Left and right sides of interval to be returned
interval_left = None
interval_right = None
if self.parent == None: # If we are at the root of the tree, then interval is unlimited
return (None, None)
# If current node is to the parent's left
if self.parent.left == self:
interval_right = self.parent.key # Upper bound is given by parent's key
if self.parent.parent != None: # If grandparent exists, it might be the lower bound
grandparent = self.parent.parent
# Check if parent is to the right of its own parent
if grandparent.right.key == self.parent.key:
# If so, then parent's parent's key is lower bound
interval_left = grandparent.key
# Else, current node is to the parent's right
else:
interval_left = self.parent.key # Lower bound is given by parent's key
if self.parent.parent != None: # If grandparent exists, it might be the upper bound
grandparent = self.parent.parent
# Check if parent is to the left of its own parent
if grandparent.left.key == self.parent.key:
# If so, then parent's parent's key is upper bound
interval_right = grandparent.key
return (interval_left, interval_right)