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.
   
   Hint:
   • 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 bfsIterator and preorderIterator methods. Completing these methods will require you to create two new iterator classes. The _BFSItertor class will use a Queue to maintain the state of the traversal between calls to next. The _PreorderItertor class will use a stack.

Finishing Up

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