;; Problem A2
(define-struct node (left right))
;; A Binary Tree of Symbols (BTS) is one of
;; -- Symbol
;; -- (make-node BTS BTS)

(define tree1 'root)
(define tree2 (make-node
               (make-node
                'here
                'there)
               'why))

;; A Binary Tree of Numbers (BTN) is one of
;; -- Number
;; -- (make-node BTN BTN)

(define tree3 314)
(define tree4 (make-node 
               42
               (make-node 3 14)))

;; A Binary Tree of ITEM (BT) is one of
;; -- ITEM
;; -- (make-node BT BT)

;; height: BT -> Number
(define (height bt)
  (cond
    [(node? bt) (+ 1 (max (height (node-left bt))
                          (height (node-right bt))))]
    [else 0]))

'height-tests
(equal? 0 (height tree1))
(equal? 2 (height tree2))

;; mix: (Listof BTS) (Listof BTS) -> (Listof BTS)
;; makes every possible tree combination with given lists, including 'leaf
(define (mix lobt1 lobt2)
  (cond
    [(empty? lobt1) (cons 'leaf empty)]
    [(cons? lobt1) (append
                    (mix-helper (first lobt1) lobt2)
                    (mix (rest lobt1) lobt2))]))

;; mix-helper: BTS (Listof BTS) -> (Listof BTS)
;; combines every element of lobt with bt
(define (mix-helper bt lobt)
  (cond
    [(empty? lobt) empty]
    [(cons? lobt) (cons
                   (make-node
                    bt
                    (first lobt))
                   (mix-helper bt (rest lobt)))]))

'mix-tests
(equal? (mix (list 'leaf (make-node 'leaf 'leaf))
             (list 'leaf (make-node 'leaf 'leaf)))
        (list
         (make-node 'leaf 'leaf)
         (make-node 'leaf (make-node 'leaf 'leaf))
         (make-node (make-node 'leaf 'leaf) 'leaf)
         (make-node (make-node 'leaf 'leaf) (make-node 'leaf 'leaf))
         'leaf))

;; create-bts: N -> (Listof BTS)
;; creates every BTS where depth <= n
(define (create-bts n)
  (cond
    [(= n 0) (cons 'leaf empty)]
    [else (mix (create-bts (sub1 n)) (create-bts (sub1 n)))]))

'create-bts-tests
(equal? (create-bts 2)
        (list
         (make-node (make-node 'leaf 'leaf) (make-node 'leaf 'leaf))
         (make-node (make-node 'leaf 'leaf) 'leaf)
         (make-node 'leaf (make-node 'leaf 'leaf))
         (make-node 'leaf 'leaf)
         'leaf))

;; filter-bt: (Listof BTS) N -> (Listof BTS)
;; filters out every BTS from lobt that is not of depth n
(define (filter-bt lobt n)
  (cond
    [(empty? lobt) empty]
    [(cons? lobt)
     (cond
       [(= (height (first lobt)) n)
        (cons (first lobt) (filter-bt (rest lobt) n))]
       [else (filter-bt (rest lobt) n)])]))

'filter-bt-test
(equal? (filter-bt (create-bts 2) 2)
        (list
         (make-node (make-node 'leaf 'leaf) (make-node 'leaf 'leaf))
         (make-node (make-node 'leaf 'leaf) 'leaf)
         (make-node 'leaf (make-node 'leaf 'leaf))))

;; all-bts: N -> (Listof BTS)
;; creates a list of every BTS of depth n
(define (all-bts n)
  (filter-bt (create-bts n) n))

'all-bts-test
(equal? (all-bts 1)
        (list (make-node 'leaf 'leaf)))