In-Class Activity #6: Binary Tree Methods

Objective

The goal today's activity is to practice working with binary trees.

Exercises

1. Download the following files:
   • binary_tree.py
   • draw_tree.py
   • llistqueue.py
   • lliststack.py
   Look over the code in the binary_tree module, run it, and make sure you understand how it works.
2. Complete the implementation of the __contains__ and count methods of the BinaryTree class. Your implementation should be recursive and should not use an iterator or one of the existing traversal methods. Test your methods to make sure that they work as expected.
   
   Hints:
   • Before you implement these methods, make sure you understand how the height method works. The logic for __contains__ and count will be very similar.
   • You may be tempted to implement __contains__ by calling count and returning True if the result is greater than 0. Don't. The goal here is to practice writing recursive tree methods. Relying on count is also less efficient: the __contains__ doesn't need to traverse the entire tree if the item is found, while count must always visit every node.
3. (If you have time.) Implement the randomAdd method according to the docstring. Test your count and __contains__ using some randomly structured trees.
   
   Hint:
   • There are at least two reasonable ways to organize the randomAdd method. You could structure it so that an empty tree is handled as a special case, and a recursive helper method is passed the root only if the root exists. This version of the method would look like the following:

          def randomAdd(self, data):
             if self._root is None:
                 self._root = _BinaryTreeNode(data)
             else:
                 self._randomAdd(self._root, data)
             self._size += 1
     

     The alternative is to create a recursive helper method that always returns the the root of the modified subtree. In this case, an empty tree is not a special case, and the random add method would look like this:

         def randomAdd(self, data):
             self._root = self._randomAdd(self._root, data)
             self._size += 1
     

Finishing Up

There is nothing to hand in for this assignment. Make sure that you save a copy of your code.