This can be done in following steps:
- Convert both trees of the sets using part(a) into ordered list.
intersection-setprocedure of ordered list from previous section to get a set in oredered list representation.
- Convert the ordered list into tree with part(b).
Clearly all of these parts are of $O(n)$ complexity. The overall complexity will be $O(n)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 (define (union-set-tree tree1 tree2) (list->tree (union-set (tree->list tree1) (tree->list tree2) ) ) ) (define (intersection-set-tree tree1 tree2) (list->tree (intersection-set (tree->list tree1) (tree->list tree2) ) ) )