Simple immutable Binary Search Tree with insertion, contains and inorder Generator. (not balanced) 'demo of yield from'

bst.py

# bst.py immutable Binary search tree (not balanced)
# using 'yield from' new in python 3.3

# start with tree = None
# nodes are a list of [value, left_tree, right_tree]
# every node is a subtree, so tree argument is a tree or subtree

def insert(tree, value):
    """ creates tree if tree is None, returns new tree"""
    if not tree:
        return (value, None, None) # top of tree
    if value < tree[0]:
        return (tree[0], insert(tree[1], value), tree[2]) # add to left
    else:
        return (tree[0], tree[1], insert(tree[2], value)) # add to right


def contains(tree, value):
    """tree is existing tree or node(subtree)"""
    if not tree:
        return False
    if value == tree[0]: # found it
        return True
    if value < tree[0]: # desend lookiing down left or right
        return contains(tree[1], value)
    else:
        return contains(tree[2], value)


def in_order(tree):
    """generate inorder sequence: tree is existing tree or node(subtree)"""
    if(tree):
        yield from in_order(tree[1])
        yield tree[0]
        yield from in_order(tree[2])
    
    
def test():
    items = ( 1, 5, 7, 2, 4, 9, 3, 12, 6, -4, 11, 22, 100, 4, 2)
    t = None
    for x in items: # build tree
        t = insert(t, x)

    assert(list(in_order(t)) == sorted(items)) # print in order
    assert(contains(t, 4) == True)
    assert(contains(t, 8) == False)
    
if __name__ == '__main__':
    test()
    print('testing done')