## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.65

## Problem

Use the results of exercises 2.63 and 2.64 to give ￼θ(*n*) implementations of `union-set` and `intersection-set` for sets implemented as (balanced) binary trees.

## Solution

(define (entry tree) (car tree)) (define (left-branch tree) (cadr tree)) (define (right-branch tree) (caddr tree)) (define (make-tree entry left right) (list entry left right)) (define (tree->list tree) (define (copy-to-list tree result-list) (if (null? tree) result-list (copy-to-list (left-branch tree) (cons (entry tree) (copy-to-list (right-branch tree) result-list))))) (copy-to-list tree '())) (define (list->tree elements) (car (partial-tree elements (length elements)))) (define (partial-tree elts n) (if (= n 0) (cons '() elts) (let ((left-size (quotient (- n 1) 2))) (let ((left-result (partial-tree elts left-size))) (let ((left-tree (car left-result)) (non-left-elts (cdr left-result)) (right-size (- n (+ left-size 1)))) (let ((this-entry (car non-left-elts)) (right-result (partial-tree (cdr non-left-elts) right-size))) (let ((right-tree (car right-result)) (remaining-elts (cdr right-result))) (cons (make-tree this-entry left-tree right-tree) remaining-elts)))))))) (define (union-set set1 set2) (define (union-set-list list1 list2) (cond ((null? list1) list2) ((null? list2) list1) (else (let ((x1 (car list1)) (x2 (car list2))) (cond ((= x1 x2) (cons x1 (union-set-list (cdr list1) (cdr list2)))) ((< x1 x2) (cons x1 (union-set-list (cdr list1) list2))) (else (cons x2 (union-set-list list1 (cdr list2))))))))) (list->tree (union-set-list (tree->list set1) (tree->list set2)))) (define (intersection-set set1 set2) (define (intersection-set-list list1 list2) (if (or (null? list1) (null? list2)) '() (let ((x1 (car list1)) (x2 (car list2))) (cond ((= x1 x2) (cons x1 (intersection-set-list (cdr list1) (cdr list2)))) ((< x1 x2) (intersection-set-list (cdr list1) list2)) ((< x2 x1) (intersection-set-list list1 (cdr list2))))))) (list->tree (intersection-set-list (tree->list set1) (tree->list set2))))

Tests:

(define s1 (list->tree '(1 2 3 5 6 8 10 11))) (define s2 (list->tree '(2 4 6 8 11 13))) (tree->list (union-set s1 s2))

*Output:*

`
`

(1 2 3 4 5 6 8 10 11 13)

(tree->list (intersection-set s1 s2))

*Output:*

`
`

(2 6 8 11)

My solutions transform the tree to a sorted list, perform the algorithms developed in the text and in exercise 2.62, and then transform the sorted list back into a tree.

Each procedure used by `union-set` or `intersection-set` to perform the operations is θ(*n*). Except for the `tree->list` transformation, which is called twice per application of `union-set` or `intersection-set`, each procedure is called once per application, so those implementations are also θ(*n*).