CS 3520 Homework 1

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]))

Part 1 — Sum

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.

Part 2 — Negate

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

Part 3 — Contains?

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.”

Part 4 — Big Leaves?

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.

Part 5 — Positive Trees?

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)

Part 6 — Optional challenge: Flatten

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?