Week 9

The topic we are working on is binary search tree for this week.  Basically, binary search tree presents the nodes in a very orderly way.  Nodes greater than the root value is in the right tree and nodes smaller than the root value is in the left tree.  Based on this special property of binary search tree, it is much more efficient to implement methods, such as finding a node.  If the item is bigger than the root value, it is certain that it is in the right subtree; if the item is smaller, it is certain that it is in the left subtree, and so on.

In the insertion and deletion function, we need to assign a new variable to the original BTNode.  After some tracing, I realized that the new variable makes an alias with the original one, so that when we change the original node's left or right subtree, the new variable is being changed as well.  That's why we can return the new variable in the end.

Based on this property, functions can be written recursively by calling recursion on either the left tree or the right tree.  In the lab, we practiced different ways of writing the same function.  

We also did Exercise 3 this week.  It is the hardest exercise I've ever done.  The sum_to_deepest function took me quite a long time.  I didn't think of using recursion involving decreasing the index over each recursion at first.  The make_tree function was not so hard to figure out at first, but the auto-marking reported minor mistakes for several times.  There are some cases that I didn't consider.  Also, even though I checked the docstring using pep8, there was still one more error reporting.  Luckily, the due date has been extended so I could fix those small problems.