+-------------------------------------+ | 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 7 ... 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))))