;;;;;;;;;;;;;;;;;;;;
;;; homework 1.1 ;;;
;;;;;;;;;;;;;;;;;;;;


;; this function returns the length
;; of the hypotenuse of a right triangle
;; with sides of length b and h
(define (pythagoras b h) 
   (sqrt (+ (* b b) (* h h)))
)

;;;;;;;;;;;;;;;;;;;;
;;; homework 1.2 ;;;
;;;;;;;;;;;;;;;;;;;;

;; This function takes a list and returns a new list with 
;; duplicate elements removed.
(define (no-duplicates l)

  ;; base case: an empty list has no duplicated.
  ;; just return the empty list.
  (if (null? l)
      '()      
      
      ;; get the head of the list into a local variable. 
      (let ((head (car l))
            (tail (cdr l))
           )
           
           ;; if the first element is in the rest of the list
           ;; then don't add it now.
           (if (member head tail)
               (no-duplicates tail)
               
               ;; otherwise, add the first element because it
               ;; is the only time this element occures in the 
               ;; list.
               (cons head (no-duplicates tail))
           )
      )
  )
)

;;;;;;;;;;;;;;;;;;;;
;;; homework 1.3 ;;;
;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; these are helper functions to get at a tree's data. ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; is the tree empty?
(define (tree-null? tree) (null? tree))

;; create a new tree with root data, as 'data', with left subtree 'left'
;; and right subtree 'right'
(define (tree-new data left right) (list data left right))

;; get the right subtree.
(define (tree-right node) (caddr node))

;; get the left subtree.
(define (tree-left node) (cadr node))

;; get the data from the root element of the tree.
(define (tree-data node) (car node))

;; this returns a new tree with all of the elements 
;; of 'l' added to 'tree'.  (this was not required
;; it just makes constructing a tree easier)
(define (tree-add-list tree l)
   (if (null? l)
       tree
       (tree-add-list (add tree (car l)) (cdr l))
   )
)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; These functions were required by the homework. ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;; this returns the subtree rooted at 'val' in 'tree'
;; if 'val' is not in 'tree' this returns ()

(define (tree-subtree tree val)
  (cond
     ((tree-null? tree) '())
     ((< val (tree-data tree)) (tree-subtree (tree-left tree) val))
     ((> val (tree-data tree)) (tree-subtree (tree-right tree) val))
     (else tree)
  )
)


;; this returns #t if 'val' is in 'tree'

(define (contains tree val)
  (cond
     ((tree-null? tree) #f)
     ((< val (tree-data tree)) (contains (tree-left tree) val))
     ((> val (tree-data tree)) (contains (tree-right tree) val))
     (else #t)
  )
)




;; this adds 'val' to 'tree'
;;    * if 'val' is alread in 'tree', it returns the same tree.

(define (add tree val)
  (cond
  
     ;; add val here.
     ((tree-null? tree) (tree-new val '() '()))
     
     ;; add val to left subtree.
     ((< val (tree-data tree))                   
        (tree-new 
           (tree-data tree) 
           (add (tree-left tree) val)
           (tree-right tree)
         )
     )
     
     ;; add val to right subtree.
     ((> val (tree-data tree))                  
        (tree-new 
           (tree-data tree) 
           (tree-left tree)
           (add (tree-right tree) val)
         )
     )
     
     
     ; tree already has val.
     (else tree)                                
  )
)
   



;; this deletes 'val' from the tree 'tree'
;;    * it is an error if 'val' is not in 'tree'
;;    * calls helper function tree-delete-root

(define (delete tree val)
  (cond
  
     ;; no such element.
     ((tree-null? tree) (error "element not found"))
     
     ;; delete val from left subtree.
     ((< val (tree-data tree)) 
         (tree-new                             
           (tree-data tree) 
           (delete (tree-left tree) val)
           (tree-right tree)
         )
     )
     
     ;; delete val from right subtree.
     ((> val (tree-data tree))                                                     
        (tree-new 
           (tree-data tree) 
           (tree-left tree)
           (delete (tree-right tree) val)
        )
     )
     
     ;; val found.
     (else (tree-delete-root tree))             
  )
)


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; these are helper functions for 'delete' ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;; this deletes the root from 'tree'
;;    * 'tree' must not be null.
;;    * this calls tree-find-min

(define (tree-delete-root tree)
  (if (tree-null? tree)
  
     ;; it is an error to call this function 
     ;; with a null tree.
     (error "tree-delete-root called on null tree")
     
     ;; lets get the data, left, and right subtrees
     ;; into local variables.
     (let 
       ((data (tree-data tree))
        (left (tree-left tree))
        (right (tree-right tree))
       )
       (cond
       
         ;; tree has no children, return
         ;; empty tree.  This line
         ;; is not necessary.  Why?
         ((and (tree-null? left) (tree-null? right)) '())
         
         
         ;; tree has no left subtree,
         ;; root deletion leaves just
         ;; right subtree.
         ((tree-null? left) right)
         
         ;; tree has no right subtree, 
         ;; root deletion leaves just
         ;; left subtree.
         ((tree-null? right) left)
         
         ;; both subtrees are not null.
         ;; delete min from right subtree
         ;; and put min as root of this tree.
         (else (let* ((min (tree-find-min right))
                      (new-right (delete right min))
                     )
                     (tree-new min left new-right)
               )
         )
       )
    )
  )
)



;; this finds the minimum element in a tree.
;;    * 'tree' must not be null.

(define (tree-find-min tree)

   ;; it is an error to call this function 
   ;; on an empty tree
   (if (tree-null? tree)
      (error "tree-find-min called on null tree")
      
      ;; get the left subtree and the data
      ;; into local variables.
      (let ((left (tree-left tree))
            (data (tree-data tree))
           )
           
           ;; if the left subtree is empty
           ;; then this is the minimum element.
           (if (tree-null? left)                   
               data                              
               
               ;; there are smaller elements in the
               ;; left subtree.  recurse.
               (tree-find-min left)                
           )
      )
   )
)