MCS 275 Spring 2022 Homework 8¶

• Course Instructor: Emily Dumas

Instructions:¶

• Complete the problems below, which ask you to write Python scripts.
• Upload your python code directly to gradescope, i.e. upload the .py files containing your work. (If you upload a screenshot or other file format, you won't get credit.)

Deadline¶

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday 8 March 2022.

Collaboration¶

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Resources you may consult¶

The course materials you may refer to for this homework are:

• Worksheet 8 Solutions
• Lecture 19 - Trees
• Lecture 20 - BST
• Lecture 21 - Traversals
• Any of the course sample programs; the ones in the trees subdirectory are of particular note.
• Downey's book
• MCS 260 course materials from Fall 2021:
  • Slides, homework, worksheets, and projects
  • Sample programs

Point distribution¶

This homework assignment has two problems, numbered 2 and 3. The grading breakdown is:

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc.. The result of these checks is shown immediately after you submit.

What to do if you're stuck¶

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 1 doesn't exist¶

In Gradescope, the score assigned to your homework submission by the autograder (checking for syntax and docstrings) will be recorded as "Problem 1". Therefore, the numbering of the actual problems begins with 2.

Prepare¶

Download trees.py from the course sample code repository and copy it to a new file hwk8.py. (It's also OK to take the modified version of trees.py you worked on in lab this week and copy it.) Both questions on this assignment ask you to make changes to this file.

Problem 2: Leaf list¶

A node of a tree is called a leaf if it has no children.

Add a method leaves to class Node in hwk8.py that, when called on the root of a tree, will find all leaf nodes in that tree and return a list of them. (So the return value should be a list of Node objects.)

Problem 3: Positive elements of BST¶

Add a method positive_keys to class BST in hwk8.py that, when called on the root of a binary search tree containing floats or integers, will return a list of all the positive keys that appear in the binary search tree.

Special grading note¶

• A correct solution that always visits every node in the tree will be worth 2 points, because visiting every node is often quite inefficient.
• For full credit, a solution must ignore parts of the tree that can't possibly contain positive keys. For example, in this binary tree: there is no need to explore the left subtree of the node with key 0, because all keys in that subtree are guaranteed to be less than or equal to 0 (i.e. NOT positive).