Possible refactoring in binary tree
As evidenced by the bug in Rev 1, the inconsistent naming between getRoot()/setRoot() and self.key is a trap that you've created for yourself.

Getters and setters would be better done using the @property decorator.  Follow the convention in the documentation:

class BinaryTree(object):
    def __init__(self, obj):
        self.obj = obj
        self.left_child = self.right_child = None

    @property
    def obj(self):
        """The datum stored in the node."""
        return self._obj

    @obj.setter
    def obj(self, value):
        self._obj = value

    def __str__(self):
        return str(self.obj)    # &lt;-- Simpler than %s interpolation

    …




Your traversal algorithms should not have a print statement, as they would be useless for anything other than printing to sys.stdout.  Instead, they should yield each result.  The caller can then choose to print them or do whatever it pleases.

for obj in pre_order(root):
    print obj




A nice way to write simple unit tests and provide documentation at the same time is to use the doctest module.