A document from MCS 275 Spring 2021, instructor Emily Dumas. You can also get the notebook file.

Worksheet 8 Solutions

MCS 275 Spring 2021 - Emily Dumas

Solutions by Jennifer Vaccaro

Topics

The main topics of this worksheet are:

  • Trees
  • Binary search trees

The main references for these topics are:

The most useful files from the sample code repository are:

Instructions

  • Problem 1 is handled differently than the others:
    • Tuesday discussion students: Problem 1 will be presented as an example at the start of discussion
    • Thursday discussion students: Please complete Problem 1 before discussion and bring your solution
  • For the other problems:
    • Work on these problems in discussion.

1. Node relationship

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:

  1. The nodes are equal
  2. One of the nodes is an ancestor of the other
  3. The nodes lie in the same tree, but neither is an ancestor of the other
  4. The nodes do not lie in the same tree

Write a function node_relationship(x,y) that takes two nodes and returns one of these strings:

  1. "equal"
  2. "ancestor"
  3. "cousin"
  4. "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.

In [4]:
# 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"
In [5]:
# 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))
equal:  equal
ancestor:  ancestor
ancestor:  ancestor
cousin:  cousin
unrelated:  unrelated

Get ready to edit 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:

2. Minimum and maximum

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.

In [ ]:
# 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
In [1]:
# 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())
                                                                                              <1>                                                                                              

                                                                                                                                              <19>                                             

                                                                                                                      <5>                                             <25>                     

                                                                                                                                  <11>                    <22>                                 

                                                                                                                            <6>         <18>                                                   

                                                                                                                               <7>   <14>                                                      

Min: <1> Max: <25>

3. Depth

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).

In [ ]:
# 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))
In [10]:
#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())
<0>

Depth: 0
      <4>      

  <1>     <9>  

        <8>    

Depth: 2
                                                                                                                                                                                              <7>                                                                                                                                                                                              

                                                                                                                                                                                                                                                                                              <26>                                                                                             

                                                                                                                                                                                                                                              <22>                                                                                            <30>                                             

                                                                                                                                                                                                                      <21>                                            <24>                                                                                                                     

                                                                                                                                                                                                          <11>                                                                                                                                                                                 

                                                                                                                                                                                                                <16>                                                                                                                                                                           

                                                                                                                                                                                                             <14>  <18>                                                                                                                                                                        

Depth: 6

4. Interval of a node

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.

In [ ]:
# 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)
In [8]:
# 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))
<0>

(None, None)
              <0>              

                      <4>      

                  <2>          

                    <3>        

<3> (2, 4)
<0> (None, None)
                                                              <34>                                                             

                              <22>                                                                                             

              <17>                            <30>                                                                             

      <4>                             <27>                                                                                     

  <2>     <11>                                                                                                                 

        <9> <12>                                                                                                                

<12> (11, None)
<34> (None, None)
In [ ]: