Quiz 8¶

MCS 275 Spring 2021 - Emily Dumas¶

Instructions:¶

Deadline¶

This quiz must be submitted in Gradescope by 12:00pm CST on Tuesday, March 9, 2021.

Topic¶

The course topics corresponding to this quiz are trees and binary search trees.

Resources you are allowed to consult¶

Quizzes are INDIVIDUAL, closed book, and only allow access to specified resources. For this quiz you can access:

• The course coding standards document
• The Python tour
• Worksheet 8 Solutions
• All of the trees sample code

Point distribution¶

There are two problems on this quiz, numbered 2 and 3. The point breakdown is:

Every problem uses module binary, none use module bst¶

The quiz questions involve binary trees, and in your solution you should import the module binary we developed in class.

The quiz questions do not involve binary search trees directly, and you must not import the module bst. (This isn't to make the questions harder; I just want to be clear that this quiz doesn't use the BST class at all.)

Submit everything in one file quiz8.py¶

Put the functions request in the problems below into a single file and upload it to Gradescope.

(One of these functions calls the other, so putting them in one file should make it easier for you to test them.)

Problem 2: Elbow test¶

A node of a binary tree is called an elbow if:

1. It has a parent node AND
1. It has exactly one child (i.e. either a left child or a right child, but not both).

For example, in the tree shown below the nodes labeled B, E, K, and G are the only elbows.

        F
       / \
      /   \
     /     \
    C       K
   / \     / 
  B   E   G
 /   /     \   
A   D       I
           / \
          H   J

Write a function is_elbow(x) that accepts one argument, x, which is either a Node object or None, and returns a boolean as follows:

• If x is a Node that is an elbow, it returns True
• Otherwise, it returns False

Problem 3: Elbow count¶

Write a recursive function elbow_count(x) that accepts a Node object x that is the root of a binary tree, and returns the total number of elbows in the tree.

For example, if called on the root node F of the example tree shown in the first problem on this quiz, elbow_count would return 4.

You can use the function is_elbow from problem 2 (even if you didn't complete that problem).

Your function should make a single pass through the tree, and should not create any data structures that grow in proportion to the number of nodes in the tree. Passing around a fixed number of objects between recursive calls is fine, but making a list of all the nodes (or all the elbows) is not.

Revision history¶

• 2021-03-07 Fix count of elbows in problem 3 example
• 2021-03-07 Fix list of elbows in problem 2 example
• 2021-03-07 Initial publication