Week 9 – Lab #8 and Exercise 3

This week's lab was better than last week's, at least for the first two BST_rec modules that we had to implement. But then we had to implement one method in the BST class and another in the _BSTNode class, and a third in the _BSTNone class, and I got kind of confused on what I should be calling. I couldn't figure out what would be different with the count_less in _BSTNone at first. In the end I realized that since every None in BST is represented by _BSTNone, and that class has a count_less method, I didn't have to write the “if...else” conditions because they would be taken care of by the methods of the different types of BSTNodes.

As for our third exercise, all I can say is that I did a lot of tracing for these functions to understand how the program should work.

For part a, I took a tree's preorder and inorder traversals, broke them down into left and right subtrees (while noting how I knew which part was the left, root, and right), and got the pre- and inorders of these subtrees, then repeated until I got to an empty tree, at which point I could backtrack and substitute a None into the new tree being made. I made several trees this way to make sure that my method of splitting the traversals was correct, then wrote the function according to how I'd done it while tracing. Then I traced through my function several times to make sure it was correct.

For part b I think that my code is longer than it needs to be, but also that it's quite clear. You could say that I had some trouble with this part; it took me at least two hours just to grasp the recursive nature of this problem, trying to understand and make use of the hint. But at one point something clicked and I proceeded to finish the function in another hour. It was that I needed to find the child with the deepest leaf. This seemed a lot more obvious after I realized it, but...well, of course. So with that, I recursively called the function on the left child (if there was no right child) or the right child (if there was no left child) or cal it on both children (if they exist) and find the one with the maximum depth and return that.