Description

1 Problem Description
In this homework, you’re going to implement a binary search tree by yourself. Your BSTree needs to have the following functions: insert(), delete(), find max(), find min(), inorder(), preorder(), postorder(), level(), leafnode(), internalnode().
There are more detailed descriptions of the functions.
insert()
The function follows the rule of the standard binary search tree. The key in each node must be greater than any key stored in the left sub-tree, and less than any key stored in the right sub-tree.
delete()
The function removes a node whose key equals the input value. Please maintain the properties of binary search tree after doing delete() operation. If the given key value is not in the current tree, don’t modify the tree. (If there are two children, replacing the node’s value with its smallest value in the right sub-tree)
find max()
The function finds the maximum value in the current binary search tree.
find min()
The function finds the minimum value in the current binary search tree. inorder()
Print the current tree in the inorder traversal sequence. You should use space(’ ’) to separate the key of each node, and the output should end up with a newline character.
preorder()
Print the current tree in the preorder traversal sequence. You should use space(’ ’) to separate the key of each node, and the output should end up with a newline character.
postorder()
Print the current tree in the postorder traversal sequence. You should use space(’ ’) to separate the key of each node, and the output should end up with a newline character.
level()
Print the height of the current tree. If the tree is empty, the height of the tree is 0. (The height of the leaf node is 0)
leafnode()
Print all leaf nodes of the current tree from the leftmost one to the rightmost one. You should use space(’ ’) to separate the key of each node, and the output should end up with a newline character.
internalnode()
Print all internal nodes of the current tree from the smallest one to the largest one. You should use space(’ ’) to separate the key of each node, and the output should end up with a newline character.
2 Input/Output Specification
We have done the input function for you. You only need to focus on the functions above.
Here is an input/output example:

Figure 1: The input(left) and output(right) formats.
3 Evaluation
We have provided a code file BSTree.py. You have to fill in the class BSTree.py which is used for testing. Write your codes in TODO.
1. Do not modify the interface of the functions, but you can add your ownfunctions.
2. Binary search tree is not always balanced.
After you finish the code, just as hw1, you can use evaluation.sh to test your code.
4 Grading policy
5 Submission
Note: If the file structure of your attachment is not correct, You will be deducted 10%.