binary_tree.ss

;; Consider an implementation of binary trees with Scheme lists,
;; as in the following example:

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

(define (left T)
	(if (= (length T) 1) ;; if 1 elem in list this is a leaf
		();; if so return empty list
		(car (cdr T)) ;; else return first sub-list which should be second element
  )
)

(define (right T)
	(if (= (length T) 1) ;; if 1 elem in list this is a leaf
		();; if so return empty list
		(car (cdr (cdr T))) ;; else return second sub-list which should be last element
  )
)

(define (val T)
	(car T)
)

;; (a) Write a recursive function (n-nodes T), which returns the number of nodes
;;     in the tree T.

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

;; (b) Write a recursive function (n-leaves T), which returns the number of leaves
;;     in the tree T.

(define (n-leaves T)
	(cond
		((null? T) 0) ; empty
		((= (n-nodes T) 1) 1) ; is a leaf
		((> (n-nodes T) 1) (+ (n-leaves (left  T)) (n-leaves (right T)))) ; not a leaf so check right and left for leafage and add it if leaf
	)
)

;; (c) The height of a tree is defined as the maximum number of nodes on a path
;;     from the root to a leaf. Write a recursive function (height T), which
;;     returns the height of the tree T.

(define (height T)
	(cond
		((null? T) 0) ; empty
		((> (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) Write a recursive function (postorder T), which returns the list of all elements
;;     in the tree T corresponding to a postorder traversal of the tree. The following example illustrates the use of this function

(define (postorder T)
	(if (not (null? T))
		(flatten (list (append (postorder (left T)) (postorder (right T))) (val T)))
		();; return empty list
	)
)

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


;; I/O:
;;   > (all-different? `(d a b z e a q))
;;   Value: #f