A document from MCS 275 Spring 2021, instructor Emily Dumas. You can also get the notebook file.

Quiz 8 Solutions

MCS 275 Spring 2021 - Emily Dumas

Solutions by Jennifer Vaccaro

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
In [5]:
# Quiz 8 Problem 2
# J Vaccaro
# I wrote this code myself

import binary

def is_elbow(x):
    """Checks whether a node x is an elbow, i.e. whether it has a parent 
    and only one child."""
    if x.parent == None:
        return False
    if x.left != None and x.right == None:
        return True
    if x.right != None and x.left == None:
        return True
    return False
In [6]:
# Question 2 test code
# Create a tree
#        A
#       / \
#      /   \
#     /     \
#    B       C
#   / \     / 
#  D   E   F
#     /     \   
#    G       H
# 
# Elbows: C, E, F

A = binary.Node("A")
B = binary.Node("B")
C = binary.Node("C")
A.set_left(B)
A.set_right(C)
D = binary.Node("D")
E = binary.Node("E")
B.set_left(D)
B.set_right(E)
F = binary.Node("F")
C.set_left(F)
G = binary.Node("G")
E.set_left(G)
H = binary.Node("H")
F.set_right(H)

print("Elbows, should be true...")
print("C: {} E: {} F: {}".format(is_elbow(C),is_elbow(E),is_elbow(F)))
print("Not elbows, should be false...")
print("A: {} B: {} D: {} G: {} H: {}".format(is_elbow(A),is_elbow(B),is_elbow(D),is_elbow(G),is_elbow(H)))
Elbows, should be true...
C: True E: True F: True
Not elbows, should be false...
A: False B: False D: False G: False H: 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, the function would return 3.

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.

In [8]:
# Quiz 8 Problem 3
# J Vaccaro
# I wrote this code myself

import binary

def elbow_count(x):
    """Counts the number of elbows in a tree descending from root node x
    recursively by counting the number of elbows 'under' each child node"""
    if x == None:
        return 0
    if is_elbow(x):
        return 1 + elbow_count(x.left) + elbow_count(x.right)
    return elbow_count(x.left) + elbow_count(x.right)
In [10]:
# Question 3 test code

print(elbow_count(A)) # 3
print(elbow_count(B)) # 1
print(elbow_count(C)) # 2
print(elbow_count(H)) # 0
3
1
2
0

Revision history

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