;; -----------------------------------------------------------------------------
;; CODE for PROBLEM 10/A2: 

(define-struct branch (left right))

;; A Parameteric Data Definition for Binary Trees 
;; ----------------------------------------------
;; A [BT X] is one of: 
;; -- X 
;; -- (make-branch [BT X] [BT X])

;; -----------------------------------------------------------------------------
;; height : [BT X] -> Number 
;; how many branches are between the (given) root and the farthest leaf
(define (height bt)
  (cond
    [(branch? bt) 
     (+ 1 (max (height (branch-left bt)) (height (branch-right bt))))]
    [else 0]))

;; -----------------------------------------------------------------------------
;; all-bts-of-height= : N -> [Listof [BT 'leaf]]
;; create a list of all binary trees of height n 
(define (all-bts-of-height= n)
  (local ((define (all-bts-of-height= n)
            (cond
              [(zero? n) (cons 'leaf empty)]
              [else (local ((define all@=n-1 (all-bts-of-height= (sub1 n)))
                            (define all@<n-1 (all-bts-of-height< (sub1 n))))
                      (union (cross-trees all@=n-1 all@=n-1)
                             (union (cross-trees all@=n-1 all@<n-1)
                                    (cross-trees all@<n-1 all@=n-1))))]))

          ;; N -> [Listof [BT 'leaf]]
          ;; create a list of all binary trees of height <= n
          (define (all-bts-of-height< n)
            (cond
              [(zero? n) (all-bts-of-height= 0)]
              [else (append (all-bts-of-height= n) ;; <=== why not union? 
                            (all-bts-of-height< (sub1 n)))])))
    (all-bts-of-height= n)))

;; -----------------------------------------------------------------------------
;; Auxiliary Functions: 

;; cross-trees : [Listof [BT 'leaf]] [Listof [BT 'leaf]] -> [Listof [BT 'leaf]]
;; pair each tree in one with each tree in two 
(define (cross-trees one two)
  (cond
    [(empty? one) empty]
    [else (union (x-one-tree (first one) two) (cross-trees (rest one) two))]))

;; x-tree : [BT 'leaf] [Listof [BT 'leaf]] -> [Listof [BT 'leaf]]
;; cross t with each tree in lst 
(define (x-one-tree t lst)
  (cond
    [(empty? lst) empty]
    [else (cons (make-branch t (first lst)) (x-one-tree t (rest lst)))]))

;; -----------------------------------------------------------------------------
;; Set Operations

;; union : [Listof X] [Listof X] -> [Listof X]
;; union together the two lists 
(define (union s t)
  (cond [(empty? s) t]
        [else (cond [(member (first s) t) (union (rest s) t)]
                    [else (cons (first s) (union (rest s) t))])]))

;; set-equal : [Listof X] [Listof X] -> Boolean
(define (set-equal s t) (and (subset s t) (subset t s)))

;; subset : [Listof X] [Listof X] -> Boolean 
(define (subset s t)
  (cond [(empty? s) true]
        [else (and (member (first s) t) (subset (rest s) t))]))
  

;; -----------------------------------------------------------------------------
;; TESTS 
'height 
(equal? (height 'one) 0)
(equal? (height (make-branch 1 2)) 1)
(equal? (height (make-branch (make-branch 'one 'three) 'two)) 2)

'set-operations
(equal? (union '(a b c) '(d a e f)) '(b c d a e f))
(equal? (subset '(a b) '(c b a)) true)
(equal? (set-equal '(a b) '(b a)) true)

'x-one-tree
(equal? (x-one-tree 'leaf (list 'leaf)) (list (make-branch 'leaf 'leaf)))

'cross-trees
(equal? (cross-trees (list 'leaf) (list 'leaf)) (list (make-branch 'leaf 'leaf)))

'all-bts 
(set-equal (all-bts-of-height= 0) (list 'leaf))
(set-equal (all-bts-of-height= 1) (list (make-branch 'leaf 'leaf)))
(set-equal (all-bts-of-height= 2) 
           (list (make-branch (make-branch 'leaf 'leaf) (make-branch 'leaf 'leaf))
                 (make-branch (make-branch 'leaf 'leaf) 'leaf)
                 (make-branch 'leaf (make-branch 'leaf 'leaf))))