in python11.1 Binary Search Tree In this assignment, you will implement a Binary Search Tree You will also need to implement a Node cl
11.1 Binary Search Tree In this assignment, you will implement a Binary Search Tree You will also need to implement a Node class. This class will not be tested, but is needed to implement the BST. Your BST must implement the following methods. You are free to implement additional helper methods. It is recommended you create your own helper methods Constructor: Creates an Empty Tree String Method: Returns the string "Empty Tree" for an empty tree. Otherwise, returns a string with the tree in Preorder, Inorder, and Postorder. When printing a Empty/Null node print out the letter N. Put a single space after each value. This means your lines will end with a single extra space. Insert: Insert value x into the tree. Insert ignores duplicated values. Do not insert doubles. find: Returns true/false if value x is in the tree A testbed is provided that will test features of your code. Remember, you can add your own helper methods. Test Bed for Binary Search Tree Class Enter Test Number (1-6): Make a Balanced Tree. Inserting: [6, 8, 4, 3, 7, 5, 9] Your Tree looks like: Preorder: 6 4 3 NN 5 NN 8 7 NN9NN Inorder: N 3N 4N5N 6 N 7 N 8 N9N Postorder: NN 3 NN 5 4 NN 7 NN 9 8 6