CMPSC 132: Programming and Computation II
Lab 5 (10 points) Due date: March 20th, 2021, 11:59 PM EST
Goal: The goal of this lab is for you to gain a deeper understanding of the binary search tree data structure by working to implement additional functionality to the BinarySearchTree class.
General instructions:
• The work in this assignment must be your own original work and be completed alone.
• The instructor and course assistants are available on Teams and with office hours to answer
any questions you may have. You may also share testing code on Teams.
• A doctest is provided to ensure basic functionality and may not be representative of the full range of test cases we will be checking. Further testing is your responsibility.
• Debugging code is also your responsibility.
• You may submit more than once before the deadline; only the latest submission will be
graded.
Assignment-specific instructions:
• Download the starter code file from Canvas. Do not change the function names or given starter code in your script.
• You are not allowed to use any other data structures to manipulate or sort data.
• You are not allowed to modify the given constructor.
• You are not allowed to use the queue functions from the Python library.
• Additional examples of functionality are provided in each function’s doctest
• If you are unable to complete a function, use the pass statement to avoid syntax errors
Submission format:
• Submit your code in a file named LAB5.py file to the Lab 5 Gradescope assignment before the due date.
• As a reminder, code submitted with syntax errors does not receive credit, please run your file before submitting.
Section 1: The BinarySearchTree class
We discussed the binary search tree data structure in part 1 of Module 6 and implemented some functionality in the hands-on lecture. Using parts of that code as your starter code, your assignment is to implement additional functionality on top of the BinarySearchTree class.
As a reminder, in the hands-on lecture we modified the Node class to have both a left and right pointer (instead of just next) to implement a tree data structure. Our Node class now looks like:
For the purposes of this assignment, you can assume that all values in the binary search tree will be unique.
Methods
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Type
Name
Description
bool
isEmpty(self)
Tests to see whether the tree is empty or not
int
numChildren(self, node_object)
Gets the number of children node_object has
int or float
getMin(self)
Gets the minimum value in the tree
int or float
getMax(self)
Gets the maximum value in the tree
bool
__contains__(self, item)
Checks if a value is present in the tree
int
getHeight(self, node_object)
Gets the height of a node in the tree
isEmpty(self) (1 pt) Tests to see whether the tree is empty or not.
Output
bool
True if the tree is empty, False otherwise.
Section 1: The BinarySearchTree class
numChildren(self, node_object) (1 pt) Checks the number of children a node has, returning an integer between 0 and 2 (inclusive). You can assume that the node exists in the tree.
Input
Node
node_object
A node in the tree
Output
int
Number of children that node has
getMin(self), getMax(self) (1 pt each) Property methods that return the minimum/maximum Node value in the tree.
__contains__(self, item) (3 pt) Checks if a value is present in the tree by overloading the in operator. If you are using recursion to implement this method, the nature of the special method does not allow modifications in the parameter list, adding a helper method to assist __contains__ could be useful.
getHeight(self, node_object) (3 pt) Gets the height of a node in the tree. You can assume that the node exists in the tree. Recursion could be helpful here. As a reminder, the height of a node is the number of edges from that node to the deepest leaf. The height of a tree is the height of the root node.
Output
int or float
The minimum/maximum value in the tree
None
None is returned if the tree is empty
Input
int or float
item
The value to check if it exists in the tree
Output
bool
True if the value is in the tree, False otherwise
Input
Node
node_object
The node to check the height of
Output
int
The height of the node in the tree