SICP Exercise 2.65

sicp

Question

Use the results of Exercise 2.63 and Exercise 64 to give \(\Theta(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 \(\Theta(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))))