Lab 7 Solution

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.



    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 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.

implement count shallower


This function returns the number of nodes in nodes with depth less than n. That means that the recursive function needs to carry around a parameter that keeps track of its depth: n itself. Notice that nodes that have depth shallower than n with respect to the root have depth shallower than n 1 with respect to the root's children.

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 other functions.

additional exercises

We include a few unit tests to increase your condence that your code in ex7.py is working.

    • test concatenate leaves basic.py

    • test count leaves basic.py

    • test sum leaves basic.py

    • test sum internal basic.py


Good practice additional exercises are to try implementing any function or method from a general    Tree

on a BinaryTree, using left and right instead of children.





































2