This week’s prep introduces a new recursive data structure, the binary search tree, which is similar to the general tree data structure we saw last week. We’ll first define what a binary search tree is, look at how to represent one in Python, and then get to work implementing recursive functions that operate on them. Note that the BinarySearchTree class will look very similar to Tree, but it has some important differences to note!
Complete the Prep 8 quiz: Binary Search Trees quiz on Quercus.
This week’s programming exercises are all about getting comfortable working with binary search trees. Please find our detailed instructions in the starter code.
Note: while we’ve provided some doctests, we haven’t provided any additional sample tests this week. However, we strongly encourage you add your own tests to verify that your code is correct!
When you’re done, submit prep8.py on MarkUs.