CPE 202Lab Week 5.docx 1
Lab Week 5: Binary Search Tree
Partially Implement Binary Search Tree
Implement the following operations for a Binary Search Tree class starting from the template provided. Use the
Class TreeNode that is provided. You may implement helper methods that make your code easier to write,
read, and understand. Test cases will be provided but you should write test cases of your own as you develop
the methods. You may use iterative or recursive functions in your implementation.
You will likely want to add setters and getters for the tree node fields other than the key field. Changing the
key of a node is equivalent to removing and inserting it and that is the safer way to do the implementation rather
than trying to move the node to reflect the change in the key.
class TreeNode:
def __init__(self, key):
self.left = None
self.right = None
self.key = key
self.data = none
def insert(self, key): inserts a node with key into the correct position if not a duplicate.
def find_successor(self): # returns the node that is the inorder successor of the node
def find_min(self): # returns min value in the tree
def find_max(self): # returns max value in the tree
def inorder_print_tree(self) # print inorder the subtree of self
def print_levels(self) #inorder traversal prints list of pairs, [key, level of the node] where root is level 0
class BinarySearchTree:
def find (self, key): # returns True if key is in a node of the tree, else False
def insert(self, newkey):
def delete(self, key) # deletes the node containing key, assumes such a node exists
def print_tree(self) # print inorder the entire tree
def is_empty(self): #returns True if tree is empty, else False
Submit one file to PolyLearn
1. binary_search_tree.py
