aaaa

# Your implementation goes here

class BinarySearchTree:
    # This is a Node class that is internal to the BinarySearchTree class
    class __Node:
        def __init__(self, val, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right

        def getVal(self):
            return self.val

        def setVal(self, newval):
            self.val = newval

        def getLeft(self):
            return self.left

        def getRight(self):
            return self.right

        def setLeft(self, newleft):
            self.left = newleft

        def setRight(self, newright):
            self.right = newright

        # This method deserves a little explanation. It does an inorder traversal
        # of the nodes of the tree yielding all the values. In this way, we get
        # the values in ascending order.
        def __iter__(self):
            if self.left != None:
                for elem in self.left:
                    yield elem
            yield self.val
            if self.right != None:
                for elem in self.right:
                    yield elem

    # Below methods of the BinarySearchTree class.
    def __init__(self):
        self.root = None

    def insert(self, val):
        # The __insert function is recursive and is not a passed a self parameter.
        # It is a # static function (not a method of the class) but is hidden inside the insert
        # function so users of the class will not know it exists.
        def __insert(root, val):
            if root == None:
                return BinarySearchTree.__Node(val)
            if val < root.getVal():
                root.setLeft( __insert(root.getLeft(), val) )
            else:
                root.setRight(__insert(root.getRight(), val))
            return root

        self.root = __insert(self.root, val)

    def search(self, val):
        def __search(root,val):
            if root == None:
                return False
            if root.getVal() == val:
                return True
            if val < root.getVal():
                return __search(root.getLeft(), val)
            return __search(root.getRight(), val)

        return __search(self.root,val)