Programming and Computation II Lab #6

CMPSC-132: Programming and Computation II

Lab #6

Read the instructions carefully before starting the assignment. Make sure your code follows the
stated guidelines to ensure full credit for your work.
Instructions:
- The work in this lab must be completed alone and must be your own.
- Download the starter code file from the LAB6 Assignment on Canvas. Do not change
the function names on your script.
- A doctest is provided as an example of code functionality. Getting the same result as the
doctest does not guarantee full credit. You are responsible for debugging and testing your
code with enough data, you can share ideas and testing code during your recitation class.
- Each function must return the output (Do not use print in your final submission, otherwise
your submissions will receive a -1 point deduction)
- Do not include test code outside any function in the upload. Printing unwanted or illformatted data to output will cause the test cases to fail. Remove all your testing code
before uploading your file (You can also remove the doctest). Do not include the
input() function in your submission.
- As a REMINDER, you are not allowed to use the internet to search for a solution or
to use code written by other students that have taken (or are currently taking) the
class
Goal:
[10 pts] In our video lecture, we discussed the Binary Search Tree data structure. In the Hands On
session, we implemented the class BinarySearchTree that adds elements into instances of that
class. Using that code as your starter code, implement the following methods into the
BinarySearchTree class:
• The property method getMin that returns the minimum Node value found in the tree. If tree
is empty, method returns None. Note that the entire tree does not need to be scanned to find
the minimum.
• getHeight(node_object) that returns the height of the given node as an integer. You can
assume the node is in the tree. Recursion could be helpful here
• isEmpty() tests to see whether the tree is empty. It needs no parameters and returns a
boolean value.
- You are not allowed to use any other data structures to copy the elements of the tree for
manipulating/sorting purposes
- You are not allowed to modify the given constructor
- For getMin, you are not allowed to use the min/max built-in methods
- You can’t use queue functions from the Python library, otherwise no credit will be given
Deliverables:
• Submit your code in a file name LAB6.py to the Lab6 GradeScope assignment before the
due date