+-------------------------------------+
                    |  The World's Greatest Tree Problems |
                    +-------------------------------------+


Problem 1

Write SUM-TREE, which takes a tree of numbers and returns the sum
of all of them:

                 (6)
                / | \
(sum-tree     /   |   \    ) => 21
            (5)  (3)  (4)
           /  \
         (1)  (2)


Problem 2

Write COUNT-NODES, which takes a tree and returns a tree that looks
like the original one, but every datum is replaced with the number of
nodes in the subtree of which it is the root, plus one for itself. 


                 (%)                     (6)
                / | \                   / | \
(count-nodes  /   |   \    ) =>       /   |   \
            (@)  (*)  ($)           (3)  (1)  (1) 
           /  \                    /  \
         (-)  (%)                (1)  (1)

                  
                  (%)                  (4)  
(count-nodes     / | \    ) =>        / | \
               /   |   \            /   |   \
             (@)  (*)  ($)        (1)  (1)  (1) 



Problem 3. 

Write FRINGE, which takes a tree and returns its fringe. The fringe is
a list of the datums of the leaves of the tree.


              (a)
             / | \
(fringe    /   |   \    ) =>  (e f b j)
         (c)  (b)  (j)
        /  \
      (e)  (f)

Problem 4.

Write DEPTH, which takes a tree and returns its depth. The depth of a 
leaf is 1. 

              (a)
             / | \
(depth     /   |   \    ) =>  3
         (c)  (b)  (j)
        /  \
      (e)  (f)



Problem 5. 

Write MAX-CHILDREN that takes a tree and returns the maximum number of children
of any node in the tree.

                    (%)
                   / | \
(max-children    /   |   \    ) =>  3
               ($)  ($)  (*)
              /  \
            (@)  (#)

Problem 6.

Write EQUAL-TREE? which takes two trees and returns #t if they are
equal, #f otherwise. Two trees are equal if they have the same number of
children at every node, and the corresponding datums are the same. 


                    (%)            (%)
                   / | \          / | \
(equal-tree?     /   |   \      /   |   \    ) =>  #f
               ($)  ($)  (*)  ($)  ($)  (*)
              /  \
            (@)  (#)


Problem 7.

Write NODES-AT-DEPTH which takes a tree and a number N. It returns a list
of the datums of the tree at depth N. The depth of the root node is one.

                      (a)
                     / | \
(nodes-at-depth    /   |   \     2 ) =>  (c b j)
                 (c)  (b)  (j)
                /  \
              (e)  (f)

                      (a)
                     / | \
(nodes-at-depth    /   |   \     1 ) =>  (a)
                 (c)  (b)  (j)
                /  \
              (e)  (f)



Problem 8.  

Write TREE-MEMBER that takes a tree and some value X. Returns #t if the
value appears as one of the datums in the tree, and #f otherwise.

                      (a)
                     / | \
(tree-member       /   |   \     'f ) =>  #t
                 (c)  (b)  (j)
                /  \
              (e)  (f)


Problem 9.

Write ANCESTOR that takes a tree and two words W1 and W2. It should
return the datum of their closest parent (or grand-parent, etc) node.
Assume W1 and W2 are in the tree.


                   (1)
                  / | \
(ancestor       /   |   \     2  7 ) =>  1
              (3)  (5)  (7)
             /  \
           (2)  (9)


                   (1)
                  / | \
(ancestor       /   |   \     2  9 ) =>  3
              (3)  (5)  (7)
             /  \
           (2)  (9)


Problem 10. 

Write SIBLINGS? that takes a tree and two Scheme values X1 and X2 that
are guaranteed to be in the tree. It should return a true value if X1
and X2 are siblings (have the same direct parent node), and false
otherwise. 


                      (1)
                     / | \
(siblings?         /   |   \     3  7 ) =>  #t
                 (3)  (5)  (7)
                /  \
              (2)  (9)


                      (1)
                     / | \
(siblings?         /   |   \     2  4 ) =>  #f
                 (3)  (5)  (7)
                /  \    \
              (2)  (9)  (4)


Problem 11.

Write the function PATH-TO, which takes a tree and a datum and 
returns a path from the root node to the datum or #f if none
exists.

                   (1)
                  / | \
(path-to        /   |   \     4 ) =>  (1 5 4)
              (3)  (5)  (7)
             /  \    \
           (2)  (9)  (4)


                   (a)
                  / | \
(path-to        /   |   \     'a ) =>  (a)
              (b)  (c)  (d)
             /  \    \
           (e)  (f)  (g)


                   (1)
                  / | \
(path-to        /   |   \     13 ) =>  #f
              (3)  (5)  (7)
             /  \    \
           (2)  (9)  (4)

                                  
                    +-------------------------------------+
                    |  The World's Greatest List Problems |
                    +-------------------------------------+


Problem 12.

Define DEEP-MEMBER:

STk> (deep-member '(1 2) '(1 ((1 2) 4)))
#t
STk> (deep-member 'hello '(1 (() hello 4)))
#t
STk> (deep-member '(hello) '(1 (() (hello))))
#t
STk> (deep-member '((1)) '(((1 2) 3 (1))))
#f

Problem 13.

Write DEEP-MEMBER using ACCUMULATE:

(define (deep-member x lst)

  
  (accumulate __________________________________________________________


              __________________________________________________________


             lst))

Problem 14.

Write DEPTH that returns the depth of the list. The depth of a list
is the depth of its deepest sublist plus 1. The depth of something that
is not a pair is zero.

STk> (depth '(1 ((1 2) 4)))
3
STk> (depth 4)
0
STk> (depth '(hello there))
1

Problem 15.

Write a function LONGEST-SUBLIST that takes a possibly nested
list and returns the longest sublist of the list. The longest
sublist *can* be the original list itself, or it can lie deeper
in the list. Assume that the longest list exists: there will not
be two lists of the same length that are longest.

STk> (longest-sublist '(2))
(2)
STk> (longest-sublist '((1) (2) (3 4)))
((1) (2) (3 4))
STk>  (longest-sublist '((1) (2) (3 4 5 6 7 8)))
(3 4 5 6 7 8)
STk>  (longest-sublist '(((1) 2 3)))
((1) 2 3)

You may use this helper only:

(define (longest l1 l2)
  (if (> (length l1) (length l2))
      l1
      l2))

Problem 16.

Write the function ARITH-EVAL which takes a list that looks like a Scheme
arithmetic expression and does the math. In other words, it returns the
number that would be returned if this list was evaluated by STk.
Remember that Scheme uses *prefix* notation: the operator comes first
and can take any number of arguments. You may assume that the argument to
ARITH-EVAL will never be null. (Hint: use the MAP and APPLY functions.)

STk> (arith-eval '(+ 2 3 (- 3 4)))
4
STk> (arith-eval '(+ (* 2 (/ 6 3) 5) 20))
40
STk> (arith-eval '(+ 3))
3
STk> (arith-eval '(- 10 (+ 28 (* -10 3))))
12

You may use the following helper only:

(define (procedurize op)
  (cond ((equal? op '+) +)
	((equal? op '-) -)
	((equal? op '*) *)
	((equal? op '/) /)
	(else (error "Unknown operator: " op))))


Problem 17.

We would like to generate a pattern like this:
1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 ...
Of course, we cannot (yet) create an infinite pattern,
but we can write a function to generate this pattern up to some
number N. In fact, you can write this function. Fill it in:

STk> (count-up 3)
(1 1 2 1 2 3)
STk> (count-up 7)
(1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 1 2 3 4 5 6 7)
STk> (count-up 4)
(1 1 2 1 2 3 1 2 3 4)
STk> (count-up 2)
(1 1 2)

(define (count-up n)


   (accumulate _______________________________________________

 
	         _______________________________________________



	         (map __________________________________________
 
	 	      (enumerate-interval 1 n))))