Lab#8

set-upOpen ?le binary tree.py and save it under a new sub-directory called lab08. This ?le provides you with a declaration of class BinaryTree, headers and docstrings for the functions you will implement. Once you have read over the init method for class BinaryTree, you are ready to proceed to the implementation of the functions below. If you have questions, call your TA over. implement parenthesize This function takes an arithmetic expression tree and produces the equivalent parenthesized expression. Read over the header and docstring for this function in binary tree.py, but don’t write any implementation until you ?ll in the steps below: 1. One of the examples in our docstring is simple enough not to require recursion. Write out an if... expression that checks for this case, and then returns the correct thing. Include an else... for when the tree is not so easy to deal with. 2. Suppose the call in the previous step gives you the correct answer according to the docstring: it returns a parenthesized string representing the arithmetic expression tree it is given. How will you combine the solutions for all the smaller instances to get a solution for BinaryTree t itself? Write code to return the correct thing. Go over these three parts with your TA. After that, ?ll in the implementation in binary tree.py, and see whether it works. implement list between This function lists the nodes with values between the start and end values. Since it acts on a binary search tree, it does this e?ciently, without traversing unnecessary nodes. Read over the header and docstring for this function in binary tree.py, but don’t write any implementation until you ?ll in the steps below: 1. One of the examples in our docstring is simple enough not to require recursion. Write out an if... expression that checks for this case, and then returns the correct thing. Include an else... for when the tree is less easy to deal with. 1 2. Suppose the call in the previous step gives you the correct answer according to the docstring: it returns a list of nodes in binary search tree that are between the start and stop values. How will you combine the solutions to all the smaller instances to get a solution for BinaryTree t itself? Write code to return the correct thing. Put this code in the else... expression that you created in the ?rst step. Go over these three parts with your TA. After that, ?ll in the implementation in binary tree.py, and see whether it works. implement list longest path This function returns a Python list with the values from a longest path in this tree. Read over the header and docstring for this function in binary tree.py, but don’t write any implementation until you ?ll in the same steps as you did for the last two functions. At the end, review the three steps with your TA before ?lling in the implementation. additional exercises Good additional exercises are to try implementing any function or method from a general Tree on a BinaryTree. As usual, the last 15 minutes of the lab will consist of a 15-minute quiz.