Due: Sunday, September 6th, 2020 11:59pm

Difficulty: ★★☆☆

The following `Tree` datatype implements a binary tree with a number in each node and leaf:

(define-type Tree (leaf [val : Number]) (node [val : Number] [left : Tree] [right : Tree]))

Implement a `sum` function that takes a tree and returns the sum of the numbers in the tree.

Example: `(sum (node 5 (leaf 6) (leaf 7)))` should produce `18`.

Implement the function `negate`, which takes a tree and returns a tree that has the same shape, but with all the numbers negated.

Example: `(negate (node 5 (leaf 6) (leaf 7)))` should produce `(node -5 (leaf -6) (leaf -7))`.

Implement the function `contains?`, which takes a tree and a number and returns `#t` if the number is in the tree, `#f` otherwise.

Example: `(contains? (node 5 (leaf 6) (leaf 7)) 6)` should produce `#t`.

The second argument to the `contains?` function is “along for the ride.”

Implement the function `big-leaves?`, which takes a tree and returns `#t` if every leaf is bigger than the sum of numbers in the path of nodes from the root that reaches the leaf.

Examples: `(big-leaves? (node 5 (leaf 6) (leaf 7)))` should produce `#t`, while `(big-leaves? (node 5 (node 2 (leaf 8) (leaf 6)) (leaf 7)))` should produce `#f` (since 6 is smaller than 5 plus 2).

The `big-leaves?` function should be a thin wrapper on another function, perhaps `bigger-leaves?`, that accumulates a sum of node values.

A tree that is just a leaf has no nodes between the leaf an the root, which means that the path from the root corresponds to an empty sequence of numbers. Conventionally, the sum of an empty sequence of numbers is defined to be `0`, because it’s convenient and consistent; that’s the intent here, too.

Implement the function `positive-trees?`, which takes a list of trees and returns `#t` if every member of the list is a positive tree, where a positive tree is one whose numbers sum to a positive value.

Hint 1: This function takes a list, not a tree, so don’t try to use the template for a tree function.

Hint 2: Use your `sum` function as a helper.

Hint 3: `(positive-trees? empty)` should produce `#t`, because there’s no tree in the empty list whose numbers sum to `0` or less.

More examples:

(test (positive-trees? (cons (leaf 6) empty)) #t) (test (positive-trees? (cons (leaf -6) empty)) #f) (test (positive-trees? (cons (node 1 (leaf 6) (leaf -6)) empty)) #t) (test (positive-trees? (cons (node 1 (leaf 6) (leaf -6)) (cons (node 0 (leaf 0) (leaf 1)) empty))) #t) (test (positive-trees? (cons (node -1 (leaf 6) (leaf -6)) (cons (node 0 (leaf 0) (leaf 1)) empty))) #f)

*CS 3520 and CS 6520 students are welcome to complete the exercise, but it does not count for extra credit.*

Implement the function `flatten`, which takes a tree and returns a list that has all numbers in the tree’s nodes and leaves. The numbers should be ordered to match an inorder travsersal of the tree, and a number that appears multiple times in the tree should appear the same number of times in the list.

Your function should run in time proportional to the size of the tree, which rules out making a list of the tree numbers using `append` on recursive calls. You may find it helpful to recur on a right subtree before a left subtree.

Hint: Does the function take a list or a tree? Which template should you use?

Last update: Tuesday, September 1st, 2020mflatt@cs.utah.edu |