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.
# MCS 275 Worksheet 8 Problem 1
# Jennifer Vaccaro
# This code was written by me and the Thursday discussion group
def parents(x):
# Helper recursive function for creating lists of parents of a node
if x.parent == None:
return []
return [x.parent] + parents(x.parent)
def node_relationship(x,y):
"""Returns a string representing the relationship between the nodes
* equal
* ancestor
* cousin
* unrelated"""
# equal if they have same key (and root, but we assume unique keys in our program)
if x == y:
return "equal"
x_parents = [x] + parents(x) # Appends x to its parents so the parent list isnt empty
y_parents = [y] + parents(y) # Same with y
# ancestors if one is in the others parent list
if y in x_parents or x in y_parents:
return "ancestor"
# cousins if they share a root
if x_parents[-1] == y_parents[-1]:
return "cousin"
# unrelated if they do not a root
return "unrelated"
# Problem 1 test code
# Creates nodes as follows
# A E
# / \
# B C
# /
# D
import binary
A = binary.Node("A")
B = binary.Node("B")
A.set_left(B)
C = binary.Node("C")
A.set_right(C)
D = binary.Node("D")
A.left.set_left(D)
E = binary.Node("E")
print("equal: ",node_relationship(A,A))
print("ancestor: ",node_relationship(B,A))
print("ancestor: ",node_relationship(A,B))
print("cousin: ",node_relationship(D,C))
print("unrelated: ",node_relationship(A,E))
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:
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.
# MCS 275 Worksheet 8 Problem 2
# Jennifer Vaccaro
# I wrote this code myself in accordance with the syllabus
# added to bst.py
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"""
# If x is not defined, then set x as the root of the tree
if x is None:
x = self.root
# If there's a right child, return its maximum
if x.right != None:
return self.maximum(x.right)
# If there's no right child, return x, since it is the maximum
return x
def minimum(self, x = None):
"""Return the minimum key node from the BST"""
# If x is not defined, then set x as the root of the tree
if x is None:
x = self.root
# If there's a left child, return its minimum
if x.left != None:
return self.minimum(x.left)
# If there's no left child, return x, since it is the maximum
return x
# Test code for problem 2
import bst
import treeutil
import treevis
T = treeutil.random_bst(nodes=10)
treevis.treeprint(T)
print("Min:", T.minimum(), "Max:",T.maximum())
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).
# MCS 275 Worksheet 8 Problem 3
# Jennifer Vaccaro
# I wrote this code myself in accordance with the syllabus
# added to 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"""
if x is None:
x = self.root
# If there's no child, then the depth is zero
if x.left is None and x.right is None:
return 0
# If there's only one child, then the depth is 1+depth(child)
if x.left is None:
return 1 + self.depth(x.right)
if x.right is None:
return 1 + self.depth(x.left)
# If there are two children, then the depth is 1+maxdepth(children)
return 1 + max(self.depth(x.left),self.depth(x.right))
#Test code for problem 3
import bst
import treeutil
import treevis
T_1 = treeutil.random_bst(nodes=1)
treevis.treeprint(T_1)
print("Depth:",T_1.depth())
T_4 = treeutil.random_bst(nodes=4)
treevis.treeprint(T_4)
print("Depth:",T_4.depth())
T_10 = treeutil.random_bst(nodes=10)
treevis.treeprint(T_10)
print("Depth:",T_10.depth())
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.
# MCS 275 Worksheet 8 Problem 4
# Jennifer Vaccaro
# I wrote this code myself in accordance with the syllabus
# added to bst.py
def interval(self, x):
"""Given a node `x`, return the minimum and maximum key values that could be
stored at `x` without violating the BST condition of its parents. The value None
is used to indicate that the range of allowable values has no upper or lower
bound."""
# Set kmin, kmax to None
kmin,kmax = None,None
# If no parents, then no boundaries on the interval
if x.parent is None:
return (kmin,kmax)
# If x has a left-parent, then its key will be kmin
if x.parent.key < x.key:
kmin = x.parent.key
# If the parent has a right-parent, then its key will be the max.
if x.parent.parent != None and x.parent.parent.key > kmin:
kmax = x.parent.parent.key
# If x has a right-parent, then its key will be kmax
if x.parent.key > x.key:
kmax = x.parent.key
# If the parent has a left-parent, then its key will be the min
if x.parent.parent != None and x.parent.parent.key < kmax:
kmin = x.parent.parent.key
# Return the interval, which has at least one integer value
return (kmin,kmax)
# Problem 4 test code
import bst
import treeutil
import treevis
T_1 = treeutil.random_bst(nodes=1)
treevis.treeprint(T_1)
print(T_1.interval(T_1.root))
T_4,x,y = treeutil.random_bst_and_node_pair(nodes=4)
treevis.treeprint(T_4)
print(x,T_4.interval(x))
print(y,T_4.interval(y))
T_10,x,y = treeutil.random_bst_and_node_pair(nodes=10)
treevis.treeprint(T_10)
print(x,T_10.interval(x))
print(y,T_10.interval(y))