CS 3520 Homework 1

Due: Wednesday, August 30th, 2023 11:59pm

Difficulty:  ★★☆☆

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

  type Tree
  | leaf(val :: Int)
  | node(val :: Int,
         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 #true if the number is in the tree, #false otherwise.

Example: contains(node(5, leaf(6), leaf(7)), 6) should produce #true.

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

Part 4 — Big Leaves

Implement the function has_big_leaves, which takes a tree and returns #true if every leaf is bigger than the sum of numbers in the path of nodes from the root that reaches the leaf.

Examples: has_big_leaves(node(5, leaf(6), leaf(7))) should produce #true, while has_big_leaves(node(5, node(2, leaf(8), leaf(6)), leaf(7))) should produce #false (since 6 is smaller than 5 plus 2).

The has_big_leaves function should be a thin wrapper on another function, perhaps has_bigger_leaves, that accumulates a sum of node values.

A tree that is just a leaf has no nodes between the leaf and 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 #true 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([]) should produce #true, because there’s no tree in the empty list whose numbers sum to 0 or less.

More examples:

  check: positive_trees(cons(leaf(6),
                             []))
         ~is #true

  check: positive_trees(cons(leaf(-6),
                             []))
         ~is #false

  check: positive_trees(cons(node(1, leaf(6), leaf(-6)),
                             []))
         ~is #true

  check: positive_trees(cons(node(1, leaf(6), leaf(-6)),
                             (cons(node(0, leaf(0), leaf(1)),
                                   []))))
         ~is #true

  check: positive_trees(cons(node(-1, leaf(6), leaf(-6)),
                             cons(node(0, leaf(0), leaf(1)),
                                  [])))
         ~is #false

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 traversal 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?