Trees

Restrictions

You must work on this homework with your assigned partner.

Canonical Binary Trees

Consider the following data definition:

(define-struct leaf [value])
(define-struct node [left right])
;; A [BinTree X] is one of:
;; - (make-leaf X)
;; - (make-node [BinTree X] [BinTree X])

Write the template and three examples of [BinTree X]

Design a function with the following signature and purpose statement:

;; tree-add-all : Number [BinTree Number] -> [BinTree Numbers]
;; (tree-add-all n tree) adds n to every value in tree

Design a function with the following signature and purpose statement:

;; tree-append-all : String [BinTree String] -> [BinTree String]
;; (tree-append-all s tree) adds s as a *suffix* to every string in the tree

Design a function that abstracts the differences between the two functions above, and rewrite them using your abstraction.
Optional challenge. Not graded, do not submit.

Design a function that abstracts the differences between your abstraction in the previous problem and the builtin map function. Use your abstraction abstraction to rewrite your abstractions. You’ll know if works if you can use it for other lists and trees too.

Organization Charts

In most organizations, employeers are arranged in a hierarchy called an “organization chart” or org-chart. For example, here is a portion of the org-chart for Northeastern.

                     Joseph E. Aoun
                     (President)
                          |
                     The Cabinet                                   
                          |
      +-------------------+-------------------+
  Karl Reid      Madeleine Estabrook    David Madigan
(Chief Inclusion  (Student Affairs)    (Academic Affairs)
    Officer)                                 |
                   +-------------------------+---------+
                   |                                   |
             Administration                      Academic Deans
                   |                                   |
                   |                  +----------------+---------------+
                   |                  |                |               | 
             Thomas Sheahan      Alan Mislove    Carmen Sceppa    Uta Poiger
        (Curriculum & Programs)    (Khoury)         (Bouve)     (Social Sciences &
                                                                     Humanities)

The people in this chart have a name (obviously) and a title. Each also has a number (possibly zero) of “direct reports” that they are responsible for. In addition, each set of direct reports is grouped together with a label. E.g., the three groups above are “The Cabinet”, “Administration”, and “Academic Affairs”.

Design data called OrgChart to represent an org-chart. One of your examples must have all the information in the org-chart picture shown above. If you wish, you may also allow people to report to other people and groups to contain other groups.
Design the function full-title that consumes an OrgChart and the name of an organization, and produces an OrgChart that adds the “(organization name)” to the title for each person in the OrgChart.
Good news! Someone has bought naming rights to an existing department. In fact, we are expecting lots of name changes in the near future. Design the function with the following signature and purpose statement:
```
;; name-change : OrgChart String String -> OrgChart
;; (name-change org old-dept-name new-dept-name) renames old-dept-name to
;; new-dept-name, for every group in the organization.
```
Design a function that abstracts the differences between the two functions above, and rewrite them using your abstraction.
Design the function num-peeps that counts how many people are in an OrgChart.

Design a function with the following signature and purpose
statement:

;; count-department : OrgChart String -> Number
;; (count-department org dept) produces the number of people in org from
;; the dept department (i.e., group name).

Design a function with the following signature and purpose statement:

;; all-departments : OrgChart -> [List-of String]
;; (all-departments org) produces the list of departments (i.e., group names) in the 
;; organization.

Design a function that abstracts the differences between the three functions above, and rewrite them using your abstraction.