Binary tree problem (searching)

[pyguy at speakeasy.net]

Hi all,

I am running into a conceptual glitch in implementing a simple binary tree class. My insertion and printing (sorting) seems to be ok, but when I search the tree, my find method isn't doing what I thought it should.

Here is the output of running my tests:

>python -i trees.py
**********************************************************************
File "trees.py", line 70, in __main__.BinaryTree.find
Failed example:
    t.find('Leo')
Expected:
    -1
Got nothing
**********************************************************************
File "trees.py", line 72, in __main__.BinaryTree.find
Failed example:
    t.find('Cancer') 
Expected:
    1
Got nothing
**********************************************************************
1 items had failures:
   2 of   7 in __main__.BinaryTree.find
***Test Failed*** 2 failures.
>>>                                                 


So it appears my find method is failing to return -1 for a missing key and 1 for any key below the root. If anyone could clue me in on why this is so, I'd appreciate it.

Here is the code (trees.py):

class BinaryTree:
    """Binary Tree"""
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.key)

    def addNode(self,key):
        if key < self.key:
            if self.left:
                self.left.addNode(key)
            else:
                self.left = BinaryTree(key)
        elif key > self.key:
            if self.right:
                self.right.addNode(key)
            else:
                self.right = BinaryTree(key)

    def printTree(self):
        """
        >>> t=BinaryTree('Capricorn')
        >>> t.addNode('Aquarius')
        >>> t.addNode('Pices')
        >>> t.addNode('Cancer')
        >>> t.printTree()
        Capricorn
        Aquarius
        Cancer
        Pices
        """
        print self.key
        if self.left:
            self.left.printTree()
        if self.right:
            self.right.printTree()
            
    def printSortedTree(self):
        """
        >>> t=BinaryTree('Capricorn')
        >>> t.addNode('Aquarius')
        >>> t.addNode('Pices')
        >>> t.addNode('Cancer')
        >>> t.printSortedTree()
        Aquarius
        Cancer
        Capricorn
        Pices
        """
        if self.left:
            self.left.printSortedTree()
        print self.key
        if self.right:
            self.right.printSortedTree()

        


    def find(self, key, child=None):
        """
        >>> t=BinaryTree('Capricorn')
        >>> t.addNode('Aquarius')    
        >>> t.addNode('Pices')
        >>> t.addNode('Cancer')
        >>> t.find('Capricorn')
        1
        >>> t.find('Leo')
        -1
        >>> t.find('Cancer') 
        1
        """
        if self.key == key:
            return 1
        elif key < self.key:
            if self.left:
                self.left.find(key)
            else:
                return -1
        elif key > self.key:
            if self.right:
                self.right.find(key)
            else:
                return -1


def _test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    _test()