BinarySearchTree

class Node():
    def __init__(self, value):
        self.value = value
        self.right = None
        self.left = None
    

class BinarySearchTree():
    def __init__(self, root_value):
        root = Node(root_value)
        self.root = root
    
    
    def insert(self, value):
        curr_node = self.root
        new_node = Node(value)
        while(1):
            if value > curr_node.value:
                # print("go right")
                if curr_node.right == None:
                    curr_node.right = new_node
                    break
                else:
                    curr_node = curr_node.right
            elif value < curr_node.value:
                # print("go left")
                if curr_node.left == None:
                    curr_node.left = new_node
                    break
                else:
                    curr_node = curr_node.left
            else:
                print("value is already in the tree")
                return False
        return True


    def lookup(self, value):
        # return Node or None
        curr_node = self.root
        
        while(curr_node != None):
            if value > curr_node.value:
                curr_node = curr_node.right
            elif value < curr_node.value:
                curr_node = curr_node.left
            else:
                return curr_node
        return curr_node



print("Hello World!")
tree = BinarySearchTree(9)
tree.insert(4)
assert(tree.insert(4) == False)
tree.insert(20)
tree.insert(1)
tree.insert(6)
tree.insert(15)
tree.insert(170)
assert((tree.lookup(170).value) == 170)
assert((tree.lookup(4).value) == 4)
assert((tree.lookup(20).value) == 20)
assert(tree.lookup(11) == None)
assert((tree.lookup(1).value) == 1)
assert((tree.lookup(6).value) == 6)
assert((tree.lookup(15).value) == 15)
assert((tree.lookup(9).value) == 9)




print("Goodbye Cruel World")