- Define a structure called an empty-tree. This should be a structure with zero fields. It is, for all intents and purposes, the same as an onion-core.
- Define a data structure called a binary-tree. The data definition for this structure should look like
;; DATA DEFINITION ;; A binary-tree is EITHER ;; - empty-tree OR ;; - (make-binary-tree number binary-tree binary-tree)
- Declare several binary-trees for testing. One should be the empty tree, and each of your other trees should have some property that you think would be worth testing. I would encourage you to have between three and five trees defined for testing. Give them awesome names.
- Write a method called sum-tree-nodes. It should consume a binary-tree and return a number. That number should be the sum of all the values in the tree.
- Write a method called sum-wonky. If the node has an even? number, then you should only sum the nodes in the right-hand side of that node. If the node is an odd? number, then you should only sum the left-hand side of that node. For example, the tree
(make-binary-tree 1 (make-binary-tree 1 (make-empty-tree) (make-empty-tree)) (make-binary-tree 1000000 (make-empty-tree) (make-empty-tree)))
will return 2. If it is not clear, draw the tree.
- Write a function called build-binary-tree. It should take one parameter, a positive number. Your function should build a tree to the depth given as a parameter. A tree of depth zero should return the empty-tree. If you are being a good computer scientist, you'll think about how many nodes are in a binary tree of depth 25 before you try testing it. Each node should carry a value equal to its distance from the leaves.
- When testing the previous problem, use sum-wonky (among any other tests you write). What is this equivalent to? What method from the previous problem set have you just created a memory-intensive version of?
UPDATE: If you prefer... if you create a tree of depth 20, and run sum-wonky over that tree, how many nodes does the function touch? What structure is that like?
These problems should, I hope, get you started, but be somewhat less grueling than the last problem set.