#!/usr/bin/python

'''
    classes.py -- a couple classes, plus a unit test

    Jeff Ondich, 24 October 2006

    We'll go over this together.
'''

class BSTNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    ''' A binary search tree class. '''
    def __init__(self):
        self.root = None

    def traverseSubtreeInOrder(self, subtreeRoot, visitFunction):
        ''' visitFunction must be callable, and must take one parameter:
            the node to be visited. '''
        if subtreeRoot:
            self.traverseSubtreeInOrder(subtreeRoot.left, visitFunction)
            visitFunction(subtreeRoot)
            self.traverseSubtreeInOrder(subtreeRoot.right, visitFunction)

    def traverse(self, visitFunction):
        self.traverseSubtreeInOrder(self.root, visitFunction)

    def addToSubtree(self, subtreeRoot, node):
        if node.key < subtreeRoot.key:
            if not subtreeRoot.left:
                subtreeRoot.left = node
            else:
                self.addToSubtree(subtreeRoot.left, node)

        elif node.key > subtreeRoot.key:
            if not subtreeRoot.right:
                subtreeRoot.right = node
            else:
                self.addToSubtree(subtreeRoot.right, node)

    def add(self, key):
        newNode = BSTNode(key)
        if not self.root:
            self.root = newNode
        else:
            self.addToSubtree(self.root, newNode)


if __name__ == '__main__':
    def printVisit(node):
        print node.key

    # Build the binary search tree
    bst = BST()
    keys = ('moose', 'ant', 'tiger', 'bat', 'zebu', 'kudu', 'emu', 'auk', 'llama', 'elk')
    for key in keys:
        bst.add(key)

    # Do an in-order traversal of the tree, just printing each node's key
    # when the node is visited.
    bst.traverse(printVisit)