class BinaryNode:
    def __init__ (self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__ (self):
        self.root = None

    def insert (self, node, sub):
        if not self.root:
            self.root = sub
            return
        elif not node.left:
            node.left = sub
        elif not node.right:
            node.right = sub

    def preordernext (self, node):
        return self.next (self.root, node)
    
    def next (self, parent, node):
        value = None
        if node.left:
            return node.left
        if node.right:
            return node.right

    def printbalance (self, node):
        left = 0
        right = 0
        balance = 0
        if node.left:
            left = self.printbalance(node.left) + 1
        if node.right:
            right = self.printbalance(node.right) + 1
        balance = abs(left - right)
        print "Balance for node: ", node.data, ": ", balance
        return balance
        
##     def balance (self, node):
##         left = 0
##         right = 0
##         if node.left:
##             left += self.balance (node.left) + 1
##         if node.right:
##             right += self.balance (node.right) + 1
##         return abs(left - right)

if __name__ == "__main__":
    tree = BinaryTree()
    tree.insert (None, BinaryNode ("Hello"))
    tree.insert (tree.root, BinaryNode ("yucky"))
    tree.insert (tree.root, BinaryNode ("world"))
    tree.insert (tree.root.left, BinaryNode (":-)"))
    tree.insert (tree.root.left, BinaryNode ("XXX"))
    tree.insert (tree.root.right, BinaryNode ("Foo"))
    tree.insert (tree.root.right, BinaryNode ("Bar"))
    tree.insert (tree.root.left.left, BinaryNode ("..."))
    tree.insert (tree.root.left.left.left, BinaryNode ("----"))
    tree.insert (tree.root.left.left.left.left, BinaryNode ("++++"))
    node = tree.preordernext (tree.root.left.right)
    if node:
        print "Found ", node.data, "for ", tree.root.left.right
    else:
        print "Nothing found"
    tree.printbalance (tree.root)