This homework assignment must be submitted in Gradescope by Noon central time on Tuesday February 27, 2024.
Collaboration is prohibited, and while working on this you should only consult the resources (books, online, etc.) listed below.
This assignment corresponds to Worksheet 7, which is about trees.
The materials you may refer to for this homework are:
This homework assignment has two problems. The grading breakdown is:
| Points | Item |
|---|---|
| 4 | Autograder syntax checks (problem 1) |
| 5 | Problem 2 |
| 5 | Problem 3 |
| 14 | Total |
Ask your instructor or TA a question by email, in office hours, or on discord.
Work in hwk7prob2.py. Import the module trees (trees.py).
Write a function forest_roots(...) that takes one argument, node_list, which is a list of Nodes. These nodes might all be in the same binary tree, or they may be scattered across several different trees. The function should return a list of the root nodes of all the trees that contain some node from node_list. Each root node should only be listed once.
Example behavior:
If node_list is empty: returns [] (empty list)
If all nodes in node_list lie in the same binary tree: returns [ R ] where R is the root node of that tree.
If node_list = [A1,A2,B] where A1 and A2 are siblings and B lies in a different binary tree, returns [ RA, RB ] where RA is the root of the tree containing A1 and A2 and RB is the root of the tree containing B.
Make sure to give the function a descriptive docstring.
Work in hwk7prob3.py. Import the module trees (trees.py).
The edges of a tree are all the pairs of nodes (p,c) where p is the parent of c. (If you draw a picture of the tree, then there is one straight line in your picture for each such pair.)
Suppose you have a binary search tree (BST) with keys that are integers. Let's say that an edge (p,c) is an increment edge if the keys of p and c differ by one. That is, either c is the left child of p and c.key+1 == p.key or c is the right child of p and p.key+1 == c.key.
Write a function num_increment_edges(T) that takes the root node T of such a BST and returns the number of increment edges. You can use any method you like (e.g. recursion or iteration).
Make sure to give the function a descriptive docstring.