CS 6510 Homework 1

Due: Thursday, January 19th, 2017 11:59pm

The following Tree datatype implements binary trees with numbers 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

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

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

Impement 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, say bigger-leaves? that accumulates a sum of node values.

Part 5 — Optional challenge: Sorted?

Impement the function sorted?, which takes a tree and determines whether it is sorted in the sense that the numbers increase (or stay the same) in a inorder travsersal of the tree.

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. Instead, you must accumulate information both on the way down the tree and from one banch to the other.


Last update: Monday, April 10th, 2017
mflatt@cs.utah.edu