Problem 3: Sets: Binary Search Trees

Recall the data definition for binary search trees:

A binary-search-tree is either:

• #f

• (make-bt val left right)
  where val is a number,
  and left and right are binary-search-trees.
  

• INVARIANT: for each node, n, in a tree, (bt-val n) is bigger than all numbers in (bt-left n) and smaller than all numbers in (bt-right n).

• (define-struct bt (val left right))

Example Set

Write Scheme code that yields a valid binary search tree for the set {8,4,2,6,10,14,12}.

Template

Create a template for functions on binary search trees.

Union

Write a function called union that computes the union of two sets, represented as binary search trees. The union of two sets is a set that contains all of the elements in both sets.

Here is a function header for union:

;; union : set-of-numbers set-of-numbers set-of-numbers
;; builds a set of the numbers contained in both s1 and s2
(define (union s1 s2)
  ...)

Invariants

Explain briefly (2-3 lines) how your function enforces the invariant on binary search trees.