SAMPLE SOLUTIONS to recitation 8: more tree problems

------------------------------------------------------------

* write a procedure (make-power-tree n) that returns a binary tree
  (i.e. a tree with two branches at each node) that is n levels deep.
  the leaf values at the bottom of the tree should be the total number
  of leaves.

  (make-power-tree 0) -> 1
  (make-power-tree 1) -> (2 2)
  (make-power-tree 2) -> ((4 4) (4 4))

(define (make-power-tree n)
  (define (helper level leaf-val)
    (if (= level 0) 
	leaf-val
	(list (helper (- level 1) (* 2 leaf-val))
	      (helper (- level 1) (* 2 leaf-val)))))
  (helper n 1))

* write a procedure (map-tree op tree) that returns a new tree, with
  each leaf replaced by (op leaf) analogous to map on lists.  An elegant
  solution uses map.

(define (map-tree op tree)
  (map (lambda (x) 
	 (if (pair? x) 
	     (map-tree op x)
	     (op x)))
       tree))

* write a procedure (fold-right-tree op init tree) that gathers the
  leaves of the trees using op, analogous to fold-right on lists.  An
  elegant solution uses map & fold-right

(define (fold-right-tree op init tree)
  (fold-right op 
	      init 
	      (map (lambda (x) 
		     (if (leaf? x) 
			 x 
			 (fold-right-tree op init x))) 
		   tree)))

* write (count-leaves tree) that counts the leaves in a tree.  It
  should use map-tree & fold-right-tree and should not call itself.

(define (count-leaves tree)
  (fold-right-tree + 0 (map-tree (lambda (x) 1) tree)))

------------------------------------------------------------