;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 2. Delete duplicates from a sorted list of numbers
(define unique
  (lambda (lst)
    (cond ((or (null? lst) (null? (cdr lst))) lst)
          ((= (car lst) (cadr lst)) (unique (cdr lst)))
          (else (cons (car lst) (unique (cdr lst)))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 3. Merge 3 sorted lists
;; Jacob Mehr's solution
(define merge
  (lambda (l1 l2 l3)
    (2merge l1 (2merge l2 l3))))  ; 2merge merges 2 sorted lists

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 4
(define is-a-leaf?
  (lambda (T)
    (and (not (empty-tree? T))
         (null? (left-subtree T))
         (null? (right-subtree T)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 5
(define count-leaves
  (lambda (T)
    (cond ((null? T) 0)
          ((is-a-leaf? T) 1)
          (else (+ (count-leaves (left-subtree T))
                   (count-leaves (right-subtree T)))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 6
(define count-internal-nodes
  (lambda (T)
    (cond ((null? T) 0)
          ((is-a-leaf? T) 0)
          (else (+ 1
                   (count-internal-nodes (left-subtree T))
                   (count-internal-nodes (right-subtree T)))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 8
(define mirror-image-tree
  (lambda (T)
    (if (null? T)
        '()
        (make-nonempty-tree (root T)
                            (mirror-image-tree (right-subtree T))
                            (mirror-image-tree (left-subtree T))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 9
(define delete-leaves
  (lambda (T)
    (cond ((null? T) '())
          ((is-a-leaf? T) '())
          (else (make-nonempty-tree (root  T)
                                    (delete-leaves (left-subtree T))
                                    (delete-leaves (right-subtree T)))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 10
(define insert
  (lambda (bst value)
    (cond ((null? bst)
           (make-singleton-tree value))
          ((and (<= value (root bst))
                (null? (left-subtree bst)))
           (make-nonempty-tree (root bst)
                               (make-singleton-tree value)
                               (right-subtree bst)))
          ((and (<= value (root bst))
                (not (null? (left-subtree bst))))
           (make-nonempty-tree (root bst)
                               (insert (left-subtree bst) value)
                               (right-subtree bst)))
          ((and (> value (root bst))
                (null? (right-subtree bst)))
           (make-nonempty-tree (root bst)
                               (left-subtree bst)
                               (make-singleton-tree value)))
          (else
           (make-nonempty-tree (root bst)
                               (left-subtree bst)
                               (insert (right-subtree bst) value))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 11
(define make-bst-with-keys
  (lambda (keys)
    (cond ((null? keys) (make-empty-tree))
          (else (insert (make-bst-with-keys (cdr keys)) (car keys))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 13
(define twice-tree
  (lambda (T)
    (cond ((null? T) (make-empty-tree))
          (else (make-nonempty-tree (* 2 (root T))
                                    (twice-tree (left-subtree T))
                                    (twice-tree (right-subtree T)))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 14
(define tree-ref
  (lambda (T k)
    (list-ref (inorder T) k)))

;; The version is inefficient.  To get a more efficient procedure, write
;; an inorder-onto version that generates an interative process.
(define inorder
  (lambda (T)
    (cond ((null? T) '())
          (else (append (inorder (left-subtree T))
                        (list (root T))
                        (inorder (right-subtree T)))))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Prob 15
(define median
  (lambda (T)
    (let* ((L (inorder T))
	   (n (length L))
	   (mid (quotient n 2)))
      (if (odd? n)
	  (list-ref L mid)
	  (/ (+ (list-ref L mid)
		(list-ref L (- mid 1)))
	     2)))))