Homework 9

Skills: 8

Due

November 15, 2026

Skills: 8

Submission

This HW, like all homeworks, is done on https://github.com and submitted on https://pawtograder.khoury.northeastern.edu. Go to Pawtograder to find the repository where the assignment should be done. The commit and push action automatically makes submissions to Pawtograder, where after a few minutes you will find automated feedback.

While there may be automated feedback for parts of the "Programming Practice" section, ALL OF YOUR GRADE IS DETERMINED BY THE ASSIGNMENT CHAT THAT OCCURS DURING THE LAB FOLLOWING THE DEADLINE (see Assignment Chats).

---

Project

There is no project work this week.

---

Programming Practice

Consider the following data definition for binary trees:

from dataclasses import dataclass

@dataclass
class Leaf[T]:
    val: T

@dataclass
class Node[T]:
    left: "BinTree[T]"
    right: "BinTree[T]"

type BinTree[T] = Leaf[T] | Node[T]

The [T] after each class name makes it generic: T stands for the type of the values stored in the leaves, which can be different for different trees. So a BinTree[float] is a tree whose leaves hold numbers, and a BinTree[str] is a tree whose leaves hold strings. The type line defines BinTree[T] to mean either a Leaf[T] or a Node[T].

The goal of this homework will be to write abstractions for working with binary trees.

PART A

Finish the data design for BinTree by writing examples for a tree storing numbers and design a template for a function that solves a problem on BinTree[T].

PART B

Problem 1

Design a function called tree_zero that takes a BinTree[float] and replaces all leaf values with 0; the structure of the tree should remain the same.

Problem 2

Design a function tree_contains that takes a string and a BinTree[str] that returns whether the string exists as a leaf.

Problem 3

Design a function tree_sum that takes a BinTree[float] and returns the sum of all the numbers in the tree.

Problem 4

While trees have more structure, like lists, they still contain elements. To demonstrate this similarity, design a function called tree_flatten that takes a binary tree and converts it into a list. When flattening a node, the resulting list should contain all leaves on the left side of the node before the leaves on the right side of the node.

For example, the flattening the tree below should result in [1, 2, 3, 4, 5, 6]:

           *
          / \
         *   6
        / \
       1   *
          / \
         *   5
        / \
       *   4
      / \
     2   3

PART C

Problem 1

Design a function called tree_map that takes a function and a binary tree and applies the function to each value in the tree. The function should return a new tree with the same structure as the original tree, but with the values replaced by the result of applying the function to the value that was originally there.

Problem 2

Design a function called tree_andmap that takes a predicate (a function from T to bool) and a BinTree[T] and determines whether all values in the tree satisfy the predicate.

Problem 3

Design a function called tree_ormap that takes a predicate (a function from T to bool) and a BinTree[T] and determines whether any of the values in the tree satisfy the predicate.

Problem 4

Design a function tree_fold that acts like a fold over a tree. This takes in a function to apply to leaf values, and a function to combine the results of folding subtrees. These two functions should be used to compress a given tree down to a single resulting value. It should have the following signature, where Callable[[A], B] is the type of a function that takes an A and returns a B (to use Callable, add from collections.abc import Callable to the top of your file):

def tree_fold[A, B](leaf_fn: Callable[[A], B], node_fn: Callable[[B, B], B], t: BinTree[A]) -> B:

A test is given below for clarity:

def test_tree_fold():
    assert tree_fold(lambda s: s.upper(), lambda a, b: a + b, Node(Leaf("hello"), Leaf("world"))) == "HELLOWORLD"