;;Miguel Muniz

;;  1)

(define (subst x y L)
   ;;(newline)
   ;;(display L)
  (cond ((null? L) L)
        (cond (eq? (car L) x) ; if head of list is equal to x
        (cons y (subst x y (cdr L)))) ;
        (else (cons (car L) (subst x y (cdr L))))))


> (subst 'c 'k '(c o c o n u t)) 
(k o k o n u t) 

;; 2)

(define (all-different?  L)
    (cond ((null? L) #t)
    ((member (car L) (cdr L)) #f)
    (else (all-different? (cdr L)))))

(define (member x L))
    (cond ((null? L) #f)
    ((eq? x (car L)) #t)
    (else (member x (cdr L)))))

;; 3)

;; tree
(define T 
  '(13  
    (5  
        (1 () ())  
        (8 ()  
            (9 () ())))  
    (22  
        (17 () ())  
        (25 () ())))) 

;; other functions
(define (left T)
	(cond (= (length T) 1) 
		(car (cdr T)) 
  ))

(define (right T)
	(cond (= (length T) 1)
		(car (cdr (cdr T)))
    ))

(define (val T)
	(car T))

;; a)

(define (n-nodes T))
    (cond ((null? T) 0) ; if empty
            (else (+ (n-nodes (left T)) (n-nodes (right T)) 1))))

;; b)
(define (n-leaves T))
    (cond ((null? T) 0)
            ((= n-nodes T) 1) 1) ;; leaf
            (else (+ (n-leaves (left T)) (n-leaves (right T))))))

;; c)
(define (height T)
    (cond ((null? T) 0)
            ((> (n-leaves (left T)) (n-leaves (right T)))
			    (+ (height (left T)) 1))
		    ((<= (n-leaves (left T)) (n-leaves (right T)))
			    (+ (height (right T)) 1))))

;; d)
(define (postorder T))
    (cond ((null? T) '())
            ((null? (cdr T)) (list (car T)))
            (else (append (postorder (car T)) (postorder (cdr T))))))


;; 4)

(define (flatten L)
    (cond ((null? L) '())
            ((null? (cdr L)) (list (car L)))
            (else (append (car L) (flatten (cdr L))))))
