class Branch:
    def __init__ (self, item=None, left= None, right= None):
        self.item = item
        self.left = left
        self.right = right
    def __repr__ (self):
        return str(self.item)

class BinarySearchTree:
    def __init__(self, root=None, title="A search tree"):
        if (not root):
            self.root = Branch()        
        self.text = title
    def __repr__(self):
        return self.text
    def add(self, item, branch=None):
        if (not branch):
            branch = self.root
            if (item.__class__ == "".__class__): item=item.lower()
        if (self.root.item == None):
            self.root.item = item
            return 0
        if (item == branch.item):
            return -1
        if (item < branch.item): 
            if (branch.left):
                return self.add(item, branch.left)
            else:
                branch.left = Branch(item)
                return 0
        if (item > branch.item): 
            if (branch.right):
                return self.add(item, branch.right)
            else:
                branch.right = Branch(item)
                return 0
        return 1
    def inside(self, item, branch=None):
        if (not branch):
            branch = self.root
            if (item.__class__ == "".__class__): item=item.lower()
        if (item == branch.item):
            return True
        if (item < branch.item): sub = branch.left
        if (item > branch.item): sub = branch.right
        if (sub): return self.inside(item, sub)
        return False
    def startswith(self, item, branch=None):
        if (not branch):
            branch = self.root
            if (item.__class__ == "".__class__): item=item.lower()
        if(branch.item.startswith(item)):
            return True
        if (item < branch.item): sub = branch.left
        if (item > branch.item): sub = branch.right
        if (sub): return self.startswith(item, sub)
        return False
    def addSortedList(self, list):
        if (list):
            self.add(list.pop(len(list)/2))
            self.addSortedList(list[0:len(list)/2])
            self.addSortedList(list[len(list)/2:len(list)])