; S. McIlraith, 2004
; Increment List

(define increment-list
  (lambda (x)
    (cond ((null? x) '())
          ((number? x) (+ x 1))
          (else (cons (increment-list (car x))
                      (increment-list (cdr x)))))))


; procedure to sum numbers up to n
(define (sum-n n)
   (cond ((zero? n) 0)
         (else (+ n (sum-n (- n 1))))
   )
)


;; procedure length
(define (length x)
   (cond ((null? x) 0)
         (else (+ 1 (length (cdr x))))
   )
)


;;; procedure to transform the elements of a list into their absolute value
;;; note we are not using let
(define (abs-list l1)
    (cond ((null? l1) '())
    (else (cons
      (if (> 0 (car l1)) (- (car l1)) (car l1))
      (abs-list (cdr l1))))
    )
)

; procedure append
(define (append l1 l2)
  (if (null? l1) l2
    (cons (car l1) (append (cdr l1) l2))
  )
)

; procedure myequal

(define (myequal? x y)
  (or (and (atom? x) (atom? y) (eq? x y))
      (and (not (atom? x)) (not (atom? y))
           (equal? (car x) (car y))
           (equal? (cdr x) (cdr y)))))


; let and let* examples


(let ((a 5)
      (b (+ a a))
      (c (+ a b)))
     (list a b c)
)


(let* ((a 5)
      (b (+ a a))
      (c (+ a b)))
     (list a b c)
)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Binary Search Tree Example



;A complete binary tree can be represented as a list with 3 elements:
     (root left-subtree right-subtree)

(define mytree
   `(dog (bird (aardvark () ()) (cat () ()))
               (possum (frog () ()) (wolf () ()))))

; TRY (car mytree)

; TRY (car (cdr mytree))


(define empty-tree?
        (lambda (tree) (null? tree)))

(define left-tree
        (lambda (tree)
           (if (empty-tree? tree) `Error
                                  (cadr tree))))

; TRY (left-tree mytree)

(define right-tree
        (lambda (tree)
           (if (empty-tree? tree) `Error
                                  (caddr tree))))

; TRY (right-tree mytree)


(define root-tree
        (lambda (tree)
           (if (empty-tree? tree) `Error
                                  (car tree))))

; TRY (root-tree mytree)

(define contains?
   (lambda (tree sym)
     (cond ((empty-tree? tree) ())
           ((equal? (root-tree tree) sym) #t)
           (else (or (contains? (left-tree tree) sym)
                     (contains? (right-tree tree) sym)
      )))))

; TRY (contains? mytree `aardvark)


; TRY (contains? mytree `elephant)

(define pre-order
   (lambda (tree)
      (if (null? tree) '()
          (cons (root-tree tree)
                (append (pre-order (left-tree tree))
                        (pre-order (right-tree tree))
       )))))

; TRY (pre-order mytree)

(define in-order
   (lambda (tree)
      (if (null? tree) '()
          (append (in-order (left-tree tree))
                  (cons (root-tree tree)
                        (in-order (right-tree tree))