Deadline: 2022-05-10 24:00

• In this task a binary search tree data structure will be programmed. A part of the implementation of the search tree is given in the program bintree.py.
  1. The binary tree is represented by the BinaryTree class. The root of the tree is contained by the root attribute. If the tree is empty, the value of this attribute is None, otherwise the root is an instance of the class TreeNode.
  2. The nodes are the instances of the TreeNode class. The values of the left and right attributes are None, if no child is there, or the TreeNode instance representing the child node.
  3. The methods of the BinaryTree class are insert, search_key, level, preorder_walk. They check if there is a root of the tree and then call on the appropriate recursion methods of the TreeNode class.
  4. The common recursive part of the insert and search_key methods is the search_node method of the TreeNode class. This searches in the tree to find the key value received as a parameter and returns the node where the search stops. This is the node that contains the value we are looking for, or if the key value is not in the tree, the node which the key value node should be the child of.
  5. The main program reads integers from a oneline file given as a command line argument, and then inserts them into the binary tree. Then print out the values in the preorder order to the standard output and calculate and print out the number of tree levels.
• Complete the file bintree.py with the missing parts!
  1. Insert the given key into the tree in the insert method of the BinaryTree. You may use search_node method of TreeNode, which returns the node that either contains the value you are looking for or the value of the node the child of which will be the value you are looking for. The use of this method is also illustrated by the search_key method of the BinaryTree class. Make sure that the insertion works on an empty binary tree or if a node is already contains the value you want to insert. In the latter case you do not insert the value, as the insertion is idempotent.
  2. Print out the values of the tree with a recursion in the preorder order to the standard output in the preorder_walk method of TreeNode.
  3. Using recursion, determine the number of levels of the tree in level method of TreeNode.
• Test the program with the binfa1.text, binfa2.text and with your own testfiles!