def entry(tree): return head(tree)

def left_branch(tree): return head(tail(tree))

def right_branch(tree): return head(tail(tail(tree)))

def make_tree(entry, left, right):
    return llist(entry, left, right)
def make_record(key, data):
    return pair(key, data)
def key(record):
    return head(record)
def data(record):
    return tail(record)
def lookup(given_key, tree_of_records):
    if is_none(tree_of_records):
        return None
    else:
        this_entry = entry(tree_of_records)
        this_key = key(this_entry)
        return (this_entry
                if given_key == this_key
                else lookup(given_key,
                            left_branch(tree_of_records))
                if given_key < this_key
                else lookup(given_key,
                            right_branch(tree_of_records)))

my_fav_planets = make_tree(
    make_record(4, "Mars"),
    make_tree(make_record(2, "Venus"),
              None,
              make_tree(make_record(3, "Earth"),
                        None, None)),
    make_tree(make_record(6, "Saturn"),
              make_tree(make_record(5, "Jupiter"),
                        None, None),
              None))

print(lookup(3, my_fav_planets))

# expected: [ 3, 'Earth' ]
