Description
learning goals
In this lab you will practice implementing recursive functions where the input is a BTNode. You may want to review lecture materials.
You should work on these on your own before Thursday, and you are encouraged to then go to your lab where you can get guidance and feedback from your TA . There will be an on-line quiz during the second hour of your lab.
set-up
Open le ex7.py and save it under a new sub-directory called lab7. This le provides you with a declaration of class BTNode, headers and docstrings for the functions you will implement. As well pylint.txt is a conguration le for python ta.
Once you have read over the init method for class BTNode, you are ready to proceed to the implemen-tation of the functions below.
implement list between
This function lists the nodes with values between the start and end values in a binary search tree without looking at any unnecessary nodes (so don’t just dump values into a Python list and process that).
Read over the header and docstring for this function in ex7.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.
-
Suppose the call in the previous step gives you the correct answer according to the docstring: it returns a list of nodes in binary 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.
After working on those three parts, ll in the implementation in ex7.py, and see whether it works. Be sure your solution uses the fact that this is a binary search tree to avoid looking at subtrees where values are smaller than start or larger than stop
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 ex7.py, but don’t write any implementation until you
ll in the same steps as you did for the last two functions.
2
