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 JWrite a function is_elbow(x) that accepts one argument, x, which is either a Node object or None, and returns a boolean as follows:
x is a Node that is an elbow, it returns TrueFalse# 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
# 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)))
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.
# 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)
# Question 3 test code
print(elbow_count(A)) # 3
print(elbow_count(B)) # 1
print(elbow_count(C)) # 2
print(elbow_count(H)) # 0