binarytree

class Node:
    def __init__(self, val, key):
        self.l = None
        self.r = None
        self.v = val
        self.key = key

class Tree:

    def __init__(self):
        self.root = None

    def getRoot(self):
        return self.root

    def add(self, val, key):
        if(self.root == None):
            self.root = Node(val, key)
        else:
            self._add(val, self.root, key)

    def _add(self, val, node, key):
        if(val < node.v):
            if(node.l != None):
                self._add(val, node.l, key)
            else:
                node.l = Node(val, key)
        else:
            if(node.r != None):
                self._add(val, node.r, key)
            else:
                node.r = Node(val, key)


    def return_key(self, val, node):
        data = node
        if(val < node.v):
            if(node.l != None):
                self.return_key(val, node.l)
            else:
                #print node.v
                return node
        else:
            if(node.r != None):
                #print node.v
                self.return_key(val, node.r)
            else:
                print node.v
                return node

    def deleteTree(self):
        # garbage collector will do this for us.
        self.root = None

    def printTree(self):
        if(self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if(node != None):
            self._printTree(node.l)
            print str(node.v) + ' '
            self._printTree(node.r)


if __name__ == '__main__':
    tree = Tree()
    tree.add(3, 10)
    tree.add(4, 20)
    tree.add(0, 30)
    tree.add(8, 40)
    tree.add(2, 50)
    #tree.printTree()
    print ((tree.find(3)).key)
    print ((tree.return_key(6, tree.getRoot())))
    #tree._printTree(Node(2))
    #tree.deleteTree()
    #tree.printTree()