## Description

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