def intersection_set(set1, set2):
    if is_none(set1) or is_none(set2):
        return None
    else:
        x1 = head(set1)
        x2 = head(set2)
        return (pair(x1, intersection_set(tail(set1), tail(set2)))
                if x1 == x2
                else intersection_set(tail(set1), set2)
                if x1 < x2
                # $\texttt{x2 < x1}$
                else intersection_set(set1, tail(set2)))
def length(items):
    return (0 if is_none(items)
            else 1 + length(tail(items)))
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 linked_list_to_tree(elements):
    return head(partial_tree(elements, length(elements)))
def partial_tree(elts, n):
    if n == 0:
        return pair(None, elts)
    else:
        left_size = (n - 1) // 2
        left_result = partial_tree(elts, left_size)
        left_tree = head(left_result)
        non_left_elts = tail(left_result)
        right_size = n - (left_size + 1)
        this_entry = head(non_left_elts)
        right_result = partial_tree(tail(non_left_elts), right_size)
        right_tree = head(right_result)
        remaining_elts = tail(right_result)
        return pair(make_tree(this_entry, left_tree, right_tree),
                    remaining_elts)
def tree_to_linked_list_2(tree):
    def copy_to_linked_list(tree, result_list):
        return (result_list
                if is_none(tree)
                else copy_to_linked_list(left_branch(tree),
                         pair(entry(tree),
                              copy_to_linked_list(right_branch(tree),
                                           result_list))))
    return copy_to_linked_list(tree, None)
def intersection_set_as_tree(set1, set2):
    list1 = tree_to_linked_list_2(set1)
    list2 = tree_to_linked_list_2(set2)
    return linked_list_to_tree(intersection_set(list1, list2))

print(tree_to_linked_list_2(intersection_set_as_tree(
                      linked_list_to_tree(llist(1, 3, 5, 8)),
                      linked_list_to_tree(llist(2, 3, 6, 8)) ) ))
