# BST implementation using TreeNode Class

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

def insertBST(rt, value):
    if (rt == None):
        return TreeNode(value)
    elif (value < rt.data):
        rt.left = insertBST(rt.left,value)
    elif (value > rt.data):
        rt.right = insertBST(rt.right,value)
    else:
        print('ERROR:', value, 'is already in the tree!')
        return rt
    return rt

'''
#non-recursive version of insert
def insertBST(root, value):
    if (root == None):
        return TreeNode(value)
    current = root
    parent = None
    while (current != None):
        parent = current
        if (value < current.data):
            current = current.left
        elif (value > current.data):
            current = current.right
        else:
            print('ERROR:', value, 'is already in the tree!')
            return root
    if (value < parent.data):
        parent.left = TreeNode(value)
    elif (value > parent.data):
        parent.right = TreeNode(value)
    return root
'''

def inBST(rt, target):
    if (rt == None):
        return False
    if (rt.data == target):
        return True
    elif (target < rt.data):
        return inBST(rt.left, target)
    else:
        return inBST(rt.right, target)

def inOrder(rt):
    if (rt != None):
        inOrder(rt.left)
        print(rt.data,end='')
        inOrder(rt.right)

def inOrderString(rt, s):
    if (rt != None):
        s = inOrderString(rt.left,s)
        s += rt.data
        s = inOrderString(rt.right,s)
    return s