SICP Exercise 2.65

2023-02-01

Question

Use the results of Exercise 2.63 and Exercise 64 to give $Θ (n)$ implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.

Answer

I may have taken the easy way out here, but the complexities of both these functions should be $Θ (n)$ :

(define (union-tree tree1 tree2)
  (let ((set1 (tree->list-2 tree1))
        (set2 (tree->list-2 tree2)))
    (list->tree (union-set set1 set2))))

(define (intersection-tree tree1 tree2)
  (let ((set1 (tree->list-2 tree1))
        (set2 (tree->list-2 tree2)))
    (list->tree (intersection-set set1 set2))))