Due: Wednesday, August 30th, 2023 11:59pm
Difficulty: ★★☆☆
From this assignment forward, your homework submissions need to include full test coverage. See the Shplait turial on testing as a video or in the manual for a reminder of how to enable DrRacket’s test-coverage checker.
The following Tree datatype implements a binary tree with a number in each node and leaf:
type Tree
| leaf(val :: Int)
| node(left :: Tree,
val :: Int,
right :: Tree)
Implement a sum function that takes a tree and returns the sum of the numbers in the tree.
Example: sum(node(leaf(5), 6, leaf(7))) should produce 18.
Implement the function absolute, which takes a tree and returns a tree where any negative number in the tree is replaced with its negation.
Example: absolute(node(leaf(5), -6, leaf(-7))) should produce node(leaf(5), 6, leaf(7)).
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(leaf(5), 6, leaf(7)), 5) should produce #true.
The second argument to the contains function is “along for the ride.”
Implement the function has_summary_leaves, which takes a tree and returns #true if every leaf’s number matches the sum of numbers in nodes in the path from the root that reaches the leaf.
Examples: has_summary_leaves(node(leaf(5), 5, node(leaf(3), -2, leaf(3)))) should produce #true, while has_summary_leaves(node(node(leaf(6), 1, leaf(8)), 5, leaf(5))) should produce #false (since 8 is is not 5+1).
The has_summary_leaves function should be a thin wrapper on another function, perhaps has_summary_plus_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.
Implement the function all_summary_trees, which takes a list of trees and returns #true if every member of the list is a tree with summary leaves in the sense of has_summary_leaves.
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 has_summary_leaves function as a helper.
Hint 3: all_summary_trees([]) should produce #true, because there’s no tree in the empty list that isn’t a summary tree.
More examples:
check: all_summary_trees(cons(leaf(0),
[]))
~is #true
check: all_summary_trees(cons(leaf(6),
[]))
~is #false
check: all_summary_trees(cons(node(leaf(1), 1, leaf(1)),
[]))
~is #true
check: all_summary_trees(cons(node(leaf(6),
6,
node(leaf(7), 1, leaf(7))),
cons(node(leaf(0), 0, leaf(0)),
[])))
~is #true
check: all_summary_trees(cons(node(leaf(6), 1, leaf(6)),
cons(node(leaf(0), 0, leaf(0)),
[])))
~is #false
CS 3520 and CS 6520 students are welcome to complete the exercise, but it does not count for extra credit.
Implement the function has_inorder_summary_leaves, which takes a tree and returns #true if every leaf’s number matches the sum of numbers in nodes that would be visited before the leaf by an inorder traversal of the tree.
Recall that an inorder traversal is one where nodes and leaves in the left branch of a node are visited before the node’s own value, and nodes and leaves in the right branch are visited afterward.
Your function must run in time proportional to the size of the tree, which rules out recursively looking into either of a node’s subtrees multiple times or with multiple functions. The intent of this constraint is not only to avoid an inefficient solution, but to make you consider a helper function that has extra information in both its arguments and its result.
check: has_inorder_summary_leaves(leaf(0))
~is #true
check: has_inorder_summary_leaves(node(leaf(0), 4, leaf(4)))
~is #true
check: has_inorder_summary_leaves(node(leaf(0), -4, leaf(-4)))
~is #true
check: has_inorder_summary_leaves(node(leaf(0), 4, leaf(3)))
~is #false
check: has_inorder_summary_leaves(node(leaf(1), 4, leaf(5)))
~is #false
check: has_inorder_summary_leaves(node(node(leaf(0), 4, leaf(4)),
-6,
node(leaf(-2), 9, leaf(7))))
~is #true
check: has_inorder_summary_leaves(node(node(leaf(0), 4, leaf(4)),
-6,
node(leaf(-2), 0, leaf(7))))
~is #false
| Last update: Friday, August 8th, 2025mflatt@cs.utah.edu |