# BST implementation with list of values

def insertBST(tree, value):
    if (tree == []):
        tree.extend([None]*2)
    position = 1
    while (position < len(tree) and tree[position] != None):
        if (value < tree[position]):
            position = position*2
        elif (value > tree[position]):
            position = position*2 + 1
        else:
            print('ERROR:', value, 'is already in the tree!')
            return
    if (position < len(tree)):
        tree[position] = value
    else:
        tree.extend([None] * len(tree)*2)
        tree[position] = value

def inOrder(tree, position):
    if (position >= len(tree) or tree[position] == None):
        return
    else:
        inOrder(tree, position*2)
        print(tree[position],end='')
        inOrder(tree, position*2 + 1)

def inOrderString(tree, position, s):
    if (position >= len(tree) or tree[position] == None):
        return s
    else:
        s = inOrderString(tree, position*2, s)
        s += tree[position]
        s = inOrderString(tree, position*2+1, s)
        return s